车辆路径问题的算法研究

王淑霞，葛金辉，熊 颖

(通化师范学院 计算机科学系，吉林 通化134001)

1 引言

车辆路径问题(Vehicle Routing Problem,VRP)是物流管理研究中的一项重要内容.车辆路径问题是由G.Dantzig[1]于1959年首先提出,它是指对一系列发货点或收货点,组织适当的行车路线,使车辆有序地通过它们,在满足一定的约束条件下(如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等),达到一定的目标(如路程最短、费用最小、时间尽量少、使用车辆尽量少等).

对于有时间窗车辆路径问题(VRPTW)，一般采用启发式算法求解，Gendreau[2]等人最先将禁忌搜索方法应用于VRP.禁忌搜索算法就是一种智能启发式算法，首先构造一系列的解,然后对所得解不断地进行改进.该算法所得到的解不一定是可行解,它们对可行性的偏离程度是通过目标函数里的惩罚函数来体现的.该算法求解过程中的邻域,是通过GENI过程得到的.禁忌搜索算法成功地应用于许多经典的VRP，它的优点是运用Taboo List这种记忆结构表，来避免搜索过程的重复，跳出局部最优解，寻找近似全局最优解.

2 问题描述

有时间窗约束的多车辆路径问题描述为:某一物流中心具有q台配送车为它的客户服务，客户的数量为N，位置及货物需求量一定，并且给定特定的时间窗，配送车具有最大载重限制，服务完最后一个客户后需要返回物流中心.用户i的货物需求为gi(i=1,2,…,N),且必须在时间窗口要求一个合适的车辆调度方案,使各车场的车辆能满足所有用户的需求,并使车辆总的运输成本最低.

在整个配送过程中有如下约束条件：

(1)一个客户只能被服务一次而且必须被服务一次.

(2)每辆配送车的配送路径上客户的货物重量的总和不能超过它的最大载重量.

(3)假设客户的时间窗是[ETi,LTi]完成,若车辆在ETi之前到达用户i处,则在此等待;如果车辆到达时间晚于LTi,用户i的需求将被延迟满足.

(4)如果配送车为客户服务的时间不在时间窗之内，可以允许它为该客户服务，但是必须施以惩罚权重，例如当车辆提前到达时，车辆到达时刻与时间窗开始时刻这段等待时间就算做时间损耗；车辆离开客户的时间如果超过了时间窗关闭时间也是一种时间损耗.dij表示从用户i到用户j的运输成本,它的含义可以是距离、费用、时间等,si表示车辆到达用户i的时间,pE表示在ETi之前到达用户i等待的单位时间成本,pL表示在LTi之后到达用户i的单位时间成本.若车辆在ETi之前到达用户i,则增加机会成本pE×(si-ETi);若车辆在ETi之后到达用户i,则增加罚金成本pL×(LTi-si)[3].

3 算法设计

3.1 数据结构

struct Roadinfo

{int carnum;//车辆的序号

double arrivetime;//车辆到达的时间

double leavetime;//车辆离开的时间

double early;//提前时间

double late;//迟到时间

double losttime;//浪费的时间};

struct Neigbour

{ char road[N];

char comproad[N];

int car;

double length;

double time;

double value;

Roadinfo rinfo[N];};//定义邻域的结构信息

Neigbour nei[NEIGBOUR_NUM+1];//定义邻域数组

struct Listoftabu

{ char road[N];

struct Listoftabu *next;

};//定义一个禁忌表的结构

Listoftabu *listhead,*listend;//禁忌表的头指针和尾指针

3.2 算法步骤

最初的研究文献中使用的解的表示采用的是有向边排列的方法，这种方法效率并不高，因此在本算法中采用了优化改进的直接排列法.客户直接排列法即对n个客户随机产生一个1～n的不重复序列来表示客户的服务顺序，数字i(1≤i≤n)表示客户i.为了将物流中心与客户更好的连接起来，先设定物流中心的节点号为0，因此在算法中解的完整表示为由0～n组成的序列，表示配送车从物流中心出发然后服务各个客户，按照配送过程的约束条件依次将客户划分到各个配送路径，每辆配送车负责一个配送路径，因此当划分配送路径时路径个数超过物流中心所有的配送车数量时，该解为不可行解.为了更好的增加算法的性能，本算法采用动态禁忌表长度，在搜索过程中根据情况调整禁忌表长度.解的评价方法：本文采用行驶距离+时间损耗的总代价作为评价值，设路径总路程为S，总时间损耗为T，则解的评价为V=S+T.求解VRP流程如图1所示.

图1 求解VRP的算法流程图

4 计算实例与结果分析

4.1 实例

笔者用C语言程序实现了上述车辆路径问题的禁忌搜索算法，并对一个由计算机随机生成的[初始解]进行了实验计算.

实例1：设在某物流中心有5台配送车辆，车辆的最大载重量均为8t，车辆一次配送的最大行驶距离都为50km，需要向20个客户送货.笔者利用计算机随机产生了物流中心和20个客户的位置坐标以及各客户的货物需求量，其中物流中心的坐标为(14.5km，13.0km)，20个客户的坐标及其货物需求量见表1.要求合理安排配送车辆的行车路线，使配送总里程最短.为简便起见，本文设各客户相互之间及物流中心与客户之间的距离均采用直线距离，该距离可根据客户和物流中心的坐标计算得到[4].

该实例包括20个客户，客户的全排列数多达2.433×1018个，受计算时间的限制，用穷举法根本无法求解.根据该问题的特点，在用禁忌搜索算法对其求解时采用了以下参数：对不可行路径的惩罚权重取500，迭代步数取400，每次迭代共搜索当前解的40个邻居，最小禁忌长度为10，最大禁忌长度为25.用禁忌搜索算法对实例1随机求解10次，得到的计算结果见表2[4].使用的机器配置是CPU：Celeron D 2.80GHZ，内存：1G，系统：windows xp sp2，编译环境：Code::Blocks 8.02.

表1 实例1的已知条件

4.2 结果和结论

表2 实例1的禁忌搜索算法计算结果

从表2可以看出：用禁忌搜索算法对实例1的10次求解中，都得到了质量很高的解，其解的平均值为107.36km，平均使用的车辆数为3.2辆.其中第3次计算得到的解的质量最高，其配送总里程为105.8km，对应的3条配送路径分别为：路径1：0-12-8-6-1-20-7-0；路径2：0-9-18-10-3-16-17-19-0；路径3：0-11-2-4-5-13-15-14-0.

通过以上实验计算，可以总结出本文构造的车辆路径问题的禁忌搜索算法的以下特点：(1)算法求得的解的质量较高；(2)算法的收敛速度较快，计算效率较高；(3)算法的稳健性较强.

参考文献：

[1]DANTZIG G,RAMSER J.The truck dispatching problem[J].Man2agement Science,1959,(6):80-91.

[2]Gendreau M.laporte G and Potvin J-Y.Metaheuristics for the Capacitated VRP[M].In:P.Toth and D.Vigo(eds).The Vehicle Routing Problem.Philadelphia,PA:SLSM Monographs on Discrete Mathematics and Applications. 2002.129-154.

[3]杨元峰，崔志明，等.有时间窗约束的多车场车辆路径问题的改进遗传算法[J].苏州大学学报(工科版),2006(4).

[4]张炯，郎茂祥.有时间窗配送车辆调度问题的禁忌搜索算法[J].北方交通大学学报，2004(2).