1. 引言
车辆路径问题最早是由Dantzig和Ramser [1] 于1959年首次提出的,并设计了基于线性规划的求解过程。目前对带时间窗同时取送货车辆路径问题的研究主要有两个方面:第一个方面是对同时取送货车辆路径模型的研究;第二个方面是对模型算法的研究。关于同时取送货车辆路径模型的研究,许多学者都对单车场确定需求的同时取送货问题进行研究过。Dethloff [2] 首次建立了VRPSDP问题的数学模型,并设计了依据行驶距离、车辆剩余载重能力、综合剩余载重能力以及径向距离惩罚四类插入原则的构造式启发算法,通过保留较多的车辆剩余承载空间,增大车辆访问剩余客户的自由。陈静 [3] 以运输成本为目标建立了确定需求的单车场同时取送货车辆路径模型,把人工费用、燃料消耗、轮胎损耗、保修费用和折旧五项成本综合考虑作为运输成本,并采用遗传算法对模型进行求解。
在求解带时间窗的同时取送货的车辆路径问题时,遗传算法和改进的遗传算法得到了国内外许多学者的广泛关注和使用。葛显龙,许茂增,王伟鑫等 [4] 针对城市多区域协同发展造成的商业中心相对分散的现状,提出“多对多”的城市网络化联合配送机制。A. Serdar Tasan和Mitsuo Gen [5] 对具有同时取货和交货的车辆路线问题,提出了一个基于遗传算法的方法来解决这个问题。为了说明所提出的方法,用参数设置来给出计算示例。
对VRPSPD问题研究均假设顾客点进行同时送货和取货服务的车辆是同质的,即车辆具有相同的装载能力、相同的固定费用、相同的最大行驶距离约束等,并且通常假设车辆数无限 [6] [7] 。但是在现实生活中,物流公司所拥有的车辆一般由一组异型的车辆组成,这些车辆具有不同装载能力、不同的单位旅行费用,使用车辆具有不同的固定成本,而且由于受资金约束,物流企业拥有的各种类型车辆数目也是有限的,同时,为了降低人力成本、车辆固定成本、车辆行驶成本、时间成本,物流公司更趋向于在确定客户服务需求的情况下同时进行送货和取货。本文作者研究车辆路径问题,即具有多车型同时取送货的车辆路径问题,采用遗传算法进行求解。
2. 问题描述与模型建立
2.1. 问题描述
根据番禺配送中心的实际作业情况,本文将传统的同时取送货的车辆路径问题进行重新定义:给定一个配送中心和多辆配送车辆,多量车辆从番禺配送中心出发,分别根据安排好的路线到各个客户处送货,同时将具有取货需求的客户的货物运回配送中心。这里配送中心送的货物是当天需要配送的货物,而运回的货物则是客户前一天需要运回的货物。要求在给定的约束条件下,合理安排车辆的行走路径,在综合考虑各车型的固定成本和可变配送成本的前提下,以总成本最小为目标,以尽可能提高车辆满载率、减少出行次数为思路,构建多车型的同时取送货的车辆路径优化模型。本文研究的车辆路径问题的假设如下:
1) 只有1个配送中心,且配送中心的地理位置已知;
2) 货物可以混装;
3) 配送中心与需求点的坐标位置及送货量和取货量均已知;
4) 各种车型的车辆数已知,且各车型的固定费用、旅行费用、车容量均已知;
5) 每辆车服务1条回路,由番禺配送中心出发最终回到番禺配送中心;
6) 每辆车在行驶中的车载质量不超过该车型的容量限制;
7) 每辆车每次的配送距离不超过该车型允许的最大行驶距离;
8) 每个需求点能且只能由同一辆车进行服务,每个客户最多被服务两次;
9) 货物在运输途中不会变质损坏;不考虑司机的工作时间;不考虑道路的通行情况;不考虑运输时的规章制度等。
2.2. 模型构建
模型参数说明:
n:客户数量,
C:客户节点集合,
;
A:所有客户点和配送中心的集合,其中
,其中D为配送中心。
设
为车辆类型集合,共K种;
mk:不同类型的车辆数,总的车辆数为
;
:k为类型车辆的车辆集合;
Qk:车辆的最大负载能力;
:第k种车型第l辆车的派车费用;
Lk:车辆的最大行驶距离;
Dij:客户i和客户j之间的处的距离;其中
;
si:客户i处的送需求量;
qi:客户i处的收需求量;
Uikl:k类型车中的第l辆离开顾客i时的载重量(
);
[ai, bi]:客户i的时间窗;
tij:客户i到客户j之间的行驶时间;
ti:客户i的服务时间;
sikl:第k类型的第l辆车到达客户i的时间;
d:等待惩罚系数,如果车辆到达i的时间早于ai;
e:迟到惩罚系数,如果车辆到达i的时间晚于bi;
Wijkl:k类型车辆中的第辆l从客户i到客户j时车上的载重量。
令决策变量xijkl定义如下,其中
。
基于以上符号和决策变量,建立如下模型:
(4.1)
Subject to:
(4.2)
(4.3)
(4.4)
(4.5)
(4.6)
(4.7)
(4.8)
(4.9)
(4.10)
(4.11)
(4.12)
(4.13)
其中,式(4.1)为目标函数,表示最小化总的行驶成本,第一部分表示车辆的运输费用,从客户i到客户j的运输费用一般与车辆行驶距离成正比;第二部分为运输车辆的固定成本之和,xoikl表示第k类型的第l辆车是否从配送中心驶向客户i;第三部分表示车辆取送货时不满足客户时间要求时的惩罚成本;式(4.2)是车流量守恒式,表示客户点i流出的车辆与客户点j流入的车辆是同一车型的同一辆车;式(4.3)表示每个顾客都必须被某种车型的车服务1次,且仅被服务1次;式(4.4)为车辆流约束,表示一辆车到达一个客户点完成服务后必须离开这个客户点;式(4.5)表示每辆车完成任务后,必须回到车场;式(4.6)表示限制每辆车所有送货量不得超过车容量;式(4.7)表示每辆货车所有取货量不得超过车容量;式(4.8)表示车辆在行驶过程中,任一顾客点的载货量都不能超过车容量;式(4.9)表示每条配送路径的长度不超过车辆1次配送的最大行驶距离;式(4.10)表示第K类型的车辆l从客户i向客户j行驶的过程中,在时间之前不能对客户j进行服务;式(4.11)为时间窗约束条件;式(4.12)确保每辆车的载货量不能超过车辆的最大负载能力;式(4.13)为决策变量的属性。
客户点的时间窗约束分为硬时间窗约束和软时间窗约束两种,前者要求车辆必须在时间窗内到达,若车辆到达客户i的时间早于ai,则配送车辆需要在i处等待,而到达时间不能晚于bi,即约束(4.11)中ε = 0,且目标函数(4.1)中的d = ∞,e = ∞;后者不要求配送车辆一定要在时间窗内到达,但是若其到达客户i的时间早于ai或晚于bi,需要支付一定的惩罚费用,即约束(4.11)中ε = 0。
3. 算例分析
现有12个需求客户,客户D表示配送中心,i表示客户编号,xi表示客户的横坐标,yi表示客户的纵坐标,si表示客户的送货量,qi表示客户的取货量(单位:吨),服务时间窗范围[ai, bi],配送中心及各客户之间的距离由表1给出,配送中心以及客户点信息由表2给出。通过表1和表2给出的配送中心以及各个客户点的信息,根据模型利用matlab工具,采用遗传算法进行迭代,迭代次数为400次,如图1所示,在迭代进行到50次以后,结果趋于稳定。利用遗传算求得表3的结果,表3给出了每辆车的具体行驶路线行车路线,行驶里程,装载量和到达客户的时间。
4. 结论
表4给出了番禺配送中心的成本优化效果对比,相比较于优化前,可以得出使用车辆数由原来的10辆减少到6辆,总成本也减少了1076.52元。可以看出在进行优化之前,番禺配送中心目前的车辆调度方案存在很大的问题,由于没有提前规划路径,导致车辆在行驶的过程中存在着迂回运输,路径规划不合理的问题,由此导致车辆行驶里程长,不能在客户规定的时间段到达客户处,从而使得客户服务水平下降。本文在基本VRPSDP模型的基础上,加入多车型和时间窗两个因素,以配送车辆总的成本为优化
![](Images/Table_Tmp.jpg)
Table 1. Distance between distribution centers and customer points and customer points
表1. 配送中心与客户点以及各客户点间的距离(km)
![](Images/Table_Tmp.jpg)
Table 2. Information on distribution centers and customer points
表2. 配送中心以及客户点信息
![](//html.hanspub.org/file/8-2330284x33_hanspub.png)
Figure 1. Genetic algorithm iterative process
图1. 遗传算法迭代过程
![](Images/Table_Tmp.jpg)
Table 3. Result of genetic algorithm calculation
表3. 遗传算法计算结果
![](Images/Table_Tmp.jpg)
Table 4. Panyu distribution center cost optimization effect
表4. 番禺配送中心成本优化效果
目标,给出T公司广州番禺配送中心同时取送货的运作模式。最后从番禺配送中心运营成本进行优化效果分析,将本文采用的同时取送货的模式得到的结果与之前采用的模式得到的结果进行比较分析,证明了本文的优化方案是切实可行并且具有明显的优化效果的。