车辆路径问题 车辆路径问题 车辆路径问题-车辆路径问题的类型[3]，车辆路径问

车辆路线问题（VRP）最早是由Dantzig和Ramser于1959年首次提出，它是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。

由此定义不难看出，旅行商问题（Traveling Saleman Problem,TSP）是VRP的特例，由于Gaery[2]已证明TSP问题是NP难题，因此，VRP也属于NP难题。

车辆路线问题自1959年提出以来，一直是网络优化问题中最基本的问题之一，由于其应用的广泛性和经济上的重大价值，一直受到国内外学者的广泛关注。车辆路线问题可以描述如下（如图1）：

设有一场站（depot），共有M 辆货车，车辆容量为Q，有N位顾客（customer），每位顾客有其需求量D。车辆从场站出发对客户进行配送服务最后返回场站，要求所有顾客都被配送，每位顾客一次配送完成，且不能违反车辆容量的限制，目的是所有车辆路线的总距离最小。车辆路线的实际问题包括配送中心配送、公共汽车路线制定、信件和报纸投递、航空和铁路时间表安排、工业废品收集等。

vrp问题_车辆路径问题 -车辆路径问题的类型[3]

一般而言车辆路线问题大致可以分为以下三种类型（Ballou，1992）：

1、相异的单一起点和单一终点。

2、相同的单一起点和终点。

3、多个起点和终点。

vrp问题_车辆路径问题 -车辆路径问题的方法[3]

关于车辆路线问题之学术研究文献众多，也提出了相当多的求解策略与方法，Bodin and Golden（1981）将众多之求解方法归纳成以下七种：

数学解析法（Exact Procedure）；

人机互动法（Interactive）；

先分群再排路线（Cluster First

爱华网本文地址 » http://www.aihuau.com/a/8104130103/187267.html