开放式车辆路径的单亲遗传禁忌搜索优化研究

陈丕影，杨斌

（1.上海海事大学信息工程学院，上海　201306；2.上海海事大学物流研究中心，上海 201306）

开放式车辆路径的单亲遗传禁忌搜索优化研究

陈丕影1，杨斌2

（1.上海海事大学信息工程学院，上海201306；2.上海海事大学物流研究中心，上海 201306）

0　引言

开放式车辆路径问题（Open VRP，OVRP）指车辆在服务完其所有客户之后，结束于最后所服务的客户点，而不必返回原出发地点的问题。OVRP在各种物流配送的路线优化中普遍存在。例如，第三方物流的挂靠车辆。因为车辆无需返回始发地，因此其行驶路线是开放的。

Brandao［1］使用禁忌搜索求解OVRP问题，钟石泉等［2］使用遗传算法求解带容量、时间窗的OVRP。李延晖［3］使用蚁群优化算法求解沿途不活的MOVRP。S.A. MirHassani，N.Abolghasemi使用粒子群优化算法求解OVRP。於世为［6］等使用遗传算法与禁忌搜索相混合的算法求解OVRP。李惠等使用单亲遗传禁忌搜索算法解决了手术的排程问题。

本文针对OVRP，提出了一种基于PGA和TS的混合优化算法。该混合算法首先使用PGA进行全局搜索，经过PGA优化后的种群，其所有个体再以一定的概率进行TS局部搜索，提高了运算速度。而TS的局部搜索使用交换算子生成邻域，而且只对同一辆车所服务的客户点进行优化。

1　问题描述与数学模型

根据配送中心与客户位置、实际的交通运输情况以及物流配送情况抽象出一个无向图，用G=（V，K，D）表示配送图，其中V、K表示节点属性，D表示边属性。V= ｛vi，0≤i≤n｝表示配送中心和客户，配送中心为v0，需要服务的客户数为n；K=｛k，1≤k≤m｝表示物流公司拥有的车辆数且车的型号以及载重量相同；D=｛dij，0≤i≤n，0≤j≤n｝表示配送中心与客户以及客户与客户之间的距离；qi（1≤i≤n）表示客户i订单需求量；Q表示每辆车的额定载重量；CFk表示车辆k的固定成本，CRk表示车辆k正常8小时上班单位时间劳动成本，COk表示车辆k加班单位时间劳动成本；Tsk表示车辆k的出发时间，Tok表示车辆k完成配送任务的时间，TRk表示车辆k正常上班时间且TRk=min（Tok-Tsk，8）；TOk表示车辆k加班时间且TOk=max（Tok-Tsk-8，0）；tij表示从i到j的车辆行驶时间且tij=；Tjk表示车辆k到达j的时间；si表示客户点i的服务时间，则 Tjk=Tik+si+tij×xijk，若

j=0，则Tjk=0。［ei，li］表示客户i的服务时间窗，p为车辆提前到达客户点的单位时间等待成本；q为车辆延迟到达客户点的单位时间惩罚成本。

车辆路径模型：

目标函数（1）表示成本最小化的车辆路径模型，主要由六部分组成，车辆行驶成本、车辆固定成本、正常上班劳动成本、加班劳动成本、早到等待成本、延迟到达惩罚成本。式（2）表示车辆载重约束。式（3）和式（4）表示每个客户只能有一辆车为其服务，且服务次数仅为一次。式（5）避免客户之间子回路。式（6）表示车辆只能由配送中心出发。式（7）表示配送车辆无需返回始发地。式（8）是典型的流守恒方程，确保每辆车路线的连续性，即车辆出入平衡。式（9）和式（10）表示0-1整数变量约束。

2　单亲遗传禁忌搜索算法

单亲遗传算法 （Partheno-Genetic Algorithm，PGA）只作用在一条染色体，与传统遗传算法原理相同，通过选择和变异繁殖后代，简化了操作流程，提高了运算效率。禁忌搜索算法（Tabu Search，TS）的核心是搜索过程具有记忆功能，因此具有较强的局部搜索能力。针对本文的问题，设计一种将PGA和TS相结合的单亲遗传禁忌搜索算法（PGATS），即避免了单亲遗传算法早熟现象的发生，又简化了操作步骤。

编码是应用遗传算法要解决的首要问题。本文采用自然数编码方式，所形成的染色体是由车辆编号和客户编号排列组成的有序字符串，每条染色体代表求解问题的一个解，即代表一条路径。例如，配送中心0需要完成一次配送任务，该项任务需将货物送至8个客户点。用1～8的自然数代表8个客户点。首先在1～8内随机生成一个序列，如｛1，4，3，6，8，5，2，7｝，然后根据客户点的需求量和车辆的装载能力进行解码，按顺序从左向右依次加入一个点，然后判断是否超出车辆的装载能力，按照加入的客户点排成一个序列，即为一条子路径。然后从未被访问的点重复此过程，获得下一条子路径，直到访问完所有客户点为止。最后用0解码先前形成的序列，即｛0，1，4，3，6，0，8，5，2，0，7｝得到3条子路径，每条子路径被称为一个基因，此处的染色体有3个基因组成，即01436，0852，07，因此得到的3条子路径为：

子路径1：配送中心0—客户点1—客户点4—客户点3—客户点6

子路径2：配送中心0—客户点8—客户点5—客户点2

子路径3：配送中心0—客户点7

PGA只通过选择和变异操作繁殖后代。文献［5］证明PGA只有在精英保留操作时才能达到全局收敛。因此本文采用精英保留和轮盘赌相结合的方法对种群中个体进行优生劣汰操作，既保证了最优个体直接遗传到下一代，又达到了算法全局收敛的效果。

移位算子采用单点移位，即按一定概率ps将一条染色体中的一个基因作移位操作，但必须满足一个限制条件，即移位操作不能导致新父节点的容量溢出。操作过程如图1所示：

图1　移位操作

倒位算子采用单点倒位，即按一定概率pi将一条染色体中的一个子串作倒位操作。此处无需判断父节点的容量溢出情况。操作过程如图2所示：

图2　倒位操作

变异算子采用单点变异，即按一定概率pv将一条染色体上的某个基因位上的基因取其同序基因集中的其它值的操作过程。由于编码方式是自然数编码，不允许出现重复的编号，采取方法是改变一个基因位的同时改变另一相同序号的基因位。操作过程如图3所示：

图3　变异操作

禁忌搜索算法将人工智能与局部邻域搜索算法相结合，搜索途中可接受劣解，因此有较强的“爬山”能力。TS邻域操作采用基因交换算子，并且只对同属于一辆车服务的客户进行局部搜索。

（1）初始化相关参数。种群规模popsize，最大遗传代数 maxgen，移位概率ps，倒位概率pi，变异概率pv，TS算法中禁忌表长度tslen，迭代搜索中保留的最好候选解个数bestnum；最大迭代步数tsloop；

（2）生成初始种群；

（3）解码并计算适应度值；

（4）按照适应度值，由精英保留和轮盘赌进行选择；

（5）按照移位概率ps移位操作；

（6）按照倒位概率pi倒位操作；

（7）按照变异概率pv变异操作；

（8）令p＝1；

（9）若是p＜=popsize，执行（10），否则转（19）；

（10）若是rand＜=Pts，执行（11）进行TS局部优化；否则转（18）；

（11）按照解码后染色体，将每辆车服务的客户点数，随机生成初始解，同时置空禁忌表；

（12）令k=1；

（13）若是k＜=tsloop，执行（14），否则执行（17）；

（14）利用交换算子对当前解产生邻域解，同时确定候选解个数为bestnum；

（15）判断候选解满足特赦准则与否。若成立，将其替换当前最好解；否则加入禁忌表，并解禁最早进入禁忌表的对象；

（16）令k=k+1，执行（13）；

（17）将TS局部优化后子路径编码组成新染色体；

（18）令p=p+1，执行（9）；

（19）gen=gen+1；

（20）若是gen＜=maxgen，则执行（3），开始下一代PGATS操作；否则停止迭代，输出最优解，即最优车辆路径。

3　试验及结果分析

由物流公司的一次配送服务对模型及算法进行验证。通过本文的OVRP模型，优化配送路径，降低配送成本。坐标为（50，50）的配送中心为10个客户服务，其中所租车辆固定成本为240元/辆，最大载重量为8t，最大行驶距离为250km，行驶速度为50km/h，单位距离行驶成本为20元/h。员工正常上班劳动成本为25元/h，加班劳动成本为40元/h，如果车辆早于时间窗的最早时间到达客户，则等待成本为30元/h，车辆晚于时间窗的最晚时间到达客户，则惩罚成本为50元/h。算法的参数设置和客户信息见表1与表2。

表1　参数设置

表2　客户信息

表3　运行结果对比

图4　最短路径收敛图

4　结语

本文对带时间窗的车辆路径问题进行了扩展，增加了工作人员的加班成本。在此情况下，建立以配送成本最小为目标的OVRP模型，并提出了一种将单亲遗传和禁忌搜索混合的优化算法对模型求解，同时与单亲遗传算法的运行结果进行比较，表明算法是可行和有效的。

［1］Brando J.A tabu search for the open vehicle routing problem［J］.European Journal of Operational Research，2004，157（3）：552-564.

［2］钟石泉，杜纲，贺国光.有时间窗的开放式车辆路径问题及其遗传算法［J］.计算机工程与应用，2006，34：201-2-4.

［3］李延晖，刘向．沿途补货的多车场开放式车辆路径问题及蚁群算法［J］．计算机集成制造系统，2008，14（3）：557-562．

［4］於世为，郭海湘，诸克军.基于GA-TS的开放式车辆路径优化算法及应用［J］.系统管理学报，2012，264-269.

［5］李茂军，童调生.单亲遗传算法及其全局收敛性分析［J］.自动化学报，1999，25（1）：68-72.

［6］李惠，蒋大奎.基于单亲遗传禁忌搜索算法的手术排程问题研究［J］.计算机应用研究，2013，699-702.

Open Vehicle Routing Problem；Partheno-Genetic Algorithm；Tabu Search Algorithm

Partheno-Genetic Tabu Search for Open Vehicle Routing Optimization

CHEN Pi-ying1，YANG Bin2
（1.College of Information Engineering，Shanghai Maritime University，Shanghai 201306；2.Logistics Research Center，Shanghai Maritime University，Shanghai 201306）

1007-1423（2015）22-0003-05

10.3969/j.issn.1007-1423.2015.22.001

陈丕影（1989-），女，山东菏泽，硕士研究生，研究方向为信息系统与电子商务

2015-04-30

2015-07-23

针对开放式车辆路径问题，建立带加班问题的车辆路径模型；提出一种基于单亲遗传和禁忌搜索（PGATS）混合的优化算法对模型求解，既能利用PGA并行计算、全局优化的优点，又能利用TS禁忌技术、局部搜索的优点。PGA采用移位、倒位、变异算子对种群进行更新，TS采用由交换算子产生的邻域解对同属于一辆车的客户点进行局部寻优。实验表明，算法在解决运输问题方面是可行和有效的。

开放式车辆路径；单亲遗传算法；禁忌搜索算法

杨斌（1975-），男，工学博士，教授，硕士生导师，研究方向为绿色物流、物联网、数据仓库与数据挖掘

For open vehicle routing problem，first establishes a vehicle path model with overtime issues；then proposesa single parent genetic and tabu search（PGATS）hybrid optimization algorithm for solving the model，not only uses the advantages of parallel computing and global optimization of PGA，but also takes advantage of TS taboo technology and local search.PGA using the shift，inversion mutation operator to update the population，TS using neighborhood solution generated by the exchange operator to belong to the same customer point of a car for local optimization.Experimental results show that the algorithm in solving transport problems is feasible and effective.