一类VRPSDP的建模及其算法设计

吴天智

重庆大学，重庆 400030

0 引言

在经济信息化的推动下，物流已被公认为提高企业竞争力的重要途径之一。而物流中一个非常重要的环节就是配送。配送的主要包括车辆的集装、分拣和运送等过程，是整个物流中效益最为关键的一环。在实际配送情形中，企业或客户会有同时送货和回收的需求。同时考虑了前向物流和逆向物流的车辆路径问题，称为同时送货和取货车辆路径问题(VRPSDP)。

1 VRPSDP 研究现状

有关送货车辆路径问题和取货车辆路径问题的研究比较多，但关于同时送货和取货车辆路径问题（VRPSDP）的研究比较少，VRPSDP 与这些问题一定程度上存在着内在联系。与VRPSDP 相似的有以下三种车辆路径问题：1）VRPB：车辆装满货物从配送中心出发，先完成客户处的所有送货任务后，然后再完成其他客户处的取货任务，最后返回配送中心。这种就是带回程的车辆路径问题(VRPB)。特别地，若只有一辆车来完成所有服务时，称该问题是回程的旅行商问题(TSPB)。对于VRPB 模型，Mingozzi 等人通过研究并用精确算法对其进行了求解；2）VRPBM∶送货任务和取货任务无先后之分，即送货和取货是混合的情形，这种情况称为混合送货和取货车辆路径问题（VRPBM）。Salhi 等人通过允许多个送货点同时插入到取货点的插入启发式算法求解了该问题，同时指出该算法改进了VRPBM 的计算结果和对同时送货和取货车辆路径问题求解思路；3）PDP：取货点和送货点在任务中是成对的，取货点在送货点之前，任务要求将取货点的货物装载后，再配送到送货点，且是由同一辆车完成客户的取货和送货任务,称这种问题为取货和送货问题 (PDP)。运用启发式算法求解该问题的学者有很多，如Madsen 等。

2 VRPSDP 的遗传算法设计

2.1 数学模型的建立

首先定义相关参数。

R = {i}，i = 0为车场(配送中心)，i = 1,2, … ,n表示客户节点。R 表示客户点的集合，其中 U = R∪ { 0}，U 为节点集合。

V 表示车辆集合，V = { k}，k = 1,2,… ,m。

Q 为车辆的载重能力。

C 为各客户点间的距离，C = {cij}, i, j ∈ U 。

α 为单位距离的运输费用。

β 车辆启用费用。

di：客户点i 的送货量，i ∈ R。

pi：客户点i 的取货量，i ∈ R。

。

yijk：车辆k 从节点i 到节点j 的载重。

运输成本最小的同时取货送货车辆路径问题数学模型如下：

其中， 1）式是车辆运输成本最小的目标函数； 2）式限定了对客户点的访问次数有且只有一次； 3）式是车辆的最大载重量约束； 4）式是出发时车辆最开始的载重要等于各个客户节点送货量的总和； 5）式表示各个客户节点的取货量等于车辆返回时的载重量；6）式表示任一客户点处，车辆的载重等于该处取货量和剩余送货量；7）式表示出发时车辆最大载重量限制；8）式表示返回时车辆最大载重量限制；9）式表示车辆在任意节点的载重为正；10）式表示送货与取货量非负，车辆最大载重能力是正数。

2.2 改进遗传算法设计

2.3 算法分析

通过实验算例验证得出，因初始解在开始阶段是随机生成的，所以其取值往往不符合最小运输成本的目标。但根据算法的搜索方式，解随着迭代计算的进行不断向最优目标收敛并逼近，该收敛过程表明本文建立的VRPSDP 模型的合理性和算法的可行性。

与基本遗传算法相比：基于传统轮盘赌选择算子的基本遗传算法，解呈现出较大波动性和较慢收敛速度。采用基于排序的多轮轮盘赌选择算子有相对较快收敛速度。此外，通过改进遗传算法能得到更符合实际要求的最优目标值，因此，改进遗传算法比基本遗传算法在VRPSDP 中具有更好的有效性和可行性。

[1]Ming0zziA,Gi0rgiS.Anexactmeth0df0rthevehic 1er0utingpr0b1emwithbackhau1s.Transp0rtati0nScien ce,1999,(33)：315-29.

[2]Sa1hiS,NagyG.Ac1usterinserti0nheuristicf0 rsing1eandmu1tip1edep0tvehic1er0utingpr0b1emswith backhau1ing.J0urna10fthe0perati0na1ResearchS0cie ty,1999,(50)：1034-1042.

[3]Madsen0B,RavnHF,RygaardJR.Asystemf0rdynamicvehi c1er0utingf0rtheC0penhagenFireFightingC0mpany.Research Rep0rt2/1993,IMS0R,1yngby,Denmark,1993.