论文部分内容阅读
一、引言
在實际配送中，车辆在配送的同时也有回收需求，即集送一体化VRP。随机需求VRP是指客户位置确定但需求量不确定，仅知道其概率分布。随着能源价格上升，节能物流得到发展，要求减少车辆在行驶过程中所产生的燃油消耗。综合考虑节能车辆路径问题和随机取货需求的研究还未引起广泛关注。本文研究软时间窗约束下，取货需求服从泊松分布的集送一体化节能配送线路优化问题，以期增加企业收益并降低能耗。
二、问题模型
以单配送中心与多个客户点之间的物流配送网络为研究对象。同类型的一组车辆装载客户所需的货物从配送中心出发，采用巡回运输方式按客户点进行配送和集货服务，最终返回配送中心。各节点位置、客户点的配送需求量已知，车辆出发前固定揽收货物量已知。在满足约束条件下，以最低成本得出运输线路决策，同时多揽收货物。
（一）假设条件
使用的车辆数不超过配送中心限制；每个客户仅被访问一次；送货与集货同时进行，服务时间忽略；距离取欧氏距离。时间窗开放后，客户回收货物是一个随机过程。参考Fleischmana[1]等人文献，假设回收过程为服从泊松分布。揽收货物为标准件，重量和数量成线性关系。
（二）符号与参数说明
C1为单位车辆固定启用成本。C0为单位距离运输费用。Cf为单位油价。sij为点i和j之间的距离。K={k=1，2，3，…，m}为车辆集合。A={（i，j），i∈N，j∈N，i≠j}代表车场、客户点之间边的集合。[Ei，Li]为客户i的服务时间窗要求。pe、pl分别为配送车辆提前到达、延迟到达的单位时间惩罚成本。Capa为车辆最大载重量。Tj为配送车辆到达客户j的时刻。Tij为车辆在弧（i，j）的行驶时间。Vij为弧（i，j）的行驶速度，取随机整数。F为单位重量货物的收件费用。g为单位件数货物的重量。di为出发前i的配送需求重量。pi为出发前i已知的揽收货物重量。αij为与弧（i，j）有关的常数。β与车型有关，ω为空车重量。Qij为弧i，j是车辆的载重量。tr为燃油转油耗系数。
决策变量xijk==1第k辆车服务客户i后连续服务客户j=0否则
（三）模型建立
min f1=C1∑mk=1xijk+∑k∈K∑（i，j）∈Asij·xijk·C0（1）
min f2=∑i∈NPTi（2）
式（1）、（2）表示行车成本和时间惩罚成本。假设客户i货物收集件数服从参数为λi·△t的泊松分布，建立集货载件数最大化目标函数。
maxR=F·g·∑i∈N，i≠0（Ti-Ei）·λi
车辆在弧i，j上行驶产生的能量消耗采用如下公式[2]：
EGij=αijω+Qij+βv2ijsij
该公式计算得出车辆在弧i，j上产生的的能耗EGij，单位焦耳，转化为kWh。1L0号柴油可提供约9.32kWh能量，柴油发动机平均燃油率约为39%，由此能量消耗转化为燃油量，计算出油耗成本。
minf3=Cf∑k∈K∑i，j∈Atr·αijω+Qij+βν2ijsij·xijk
式（3）转化为maxR=-minR，对4个优化目标进行线性加和转化为新目标函数Z。
minZ=f1+f2-R+f3
∑mk=1∑ni=0xijk=1j∈V＼{0}
∑mk=1∑nj=0xijk=1i∈V＼{0}
∑i∈NXi0k=∑j∈NX0jk≤mk∈K
∑i∈S∑j∈Sxij≤S-1，≤S≤n-2， SN
PTi=maxpeLi-Ti，0，pl（Ti-Ei）i∈N
Tij=dijvij
Tj=Ti+Tij
∑ni=1∑nj=1dixijk≤Capak∈K
∑ni=1∑nj=1pi+gTi-Eiλixijk≤Capak∈K
djxijk+pi+gTi-Eiλixijk≤Qij≤Capa-dixijk
∑nj=1Q0j=∑nj=1dj
式（7）、（8）为客户点的访问唯一性约束；式（9）表示所有车辆从车场出发，配送完后返回配送中心；式（10）保证不产生任何子回路。式（11）表示车辆的时间惩罚成本；式（12）表示车辆从节点i到j的行驶时间；式（13）表示到达j的时间。式（15）表示出发时，正向配送需求重量约束；式（16）表示返回时，揽收货物重量约束；式（17）表示车辆在i，j弧上的载重约束；式（18）保证出发时装载货物总和满足客户需求。
三、模型求解
PSO算法在解决车辆路径问题上十分高效，贪心算法在处理约束条件时快速简便，本文设计基于贪心算法的PSO算法优化车辆行驶路线。首先生成车辆服务客户序列，其次引入贪心算法对不满足车约束的方案进行调整，最后返回优化路径。每个粒子位置的具体编码由两部分构成：X为车辆使用情况的K维向量，位置编码取0或1分别代表未选用和选用；Y为车辆行驶路线的K×N维矩阵，N为客户数。对调整后的客户序列计算粒子适应度值，对不满足约束条件的粒子适应度值施加惩罚值M。运行结束所得全局最优值gbest 四、实验结果分析
选取测试算例[3]，节点坐标、客户需求量等来自经典算例。αij=0.0981，β=2.1，v是取[40，80]上的随机整数。车场坐标（40，40），客户数20，车辆数6，车辆自重2.7吨，最大载重量1.5吨。算法最大迭代次数200，种群规模100，加速系数c1=c2=2.05；粒子惯性权重w1=0.729。对算例重复仿真20次，统计最佳适应度值，见表1。
最优解对应的车辆总行驶成本4882元，燃油消耗成本378元，不满足软时间窗的惩罚成本259元。6辆车均被选用，行车路径为：车辆1：0-12-30-4-29-22-1-0；车辆2：0-7-18-3-0；车辆3：0-21-14-19-27-13-0；车辆4：0-28-8-11-0；车辆5：0-26-25-10-24-15-20-2-17-0；车辆6：0-16-5-23-9-6-0。
为验证优化效果，另设计不考虑动态集货数量和油耗费用的配送行驶方案并进行求解。在相同运行环境下，重复运行5次所得最优结果见表2。
根据上表可知，综合考虑集货需求和油耗两个因素后，配送成本上升，但集货收益增加，更好满足客户的集货需求，且几乎实现车辆满载，油耗费用降低。
综上所述，揽收货物需求、降低能耗的差异性，在一定程度上对物流配送线路均存在影响。节省油耗成本又增加集货收益的同时，往往又提升其他配送成本，而客户的满意率也受到影响。因此，物流企业根据实际情况制定决策方案时，需考虑如何在节约成本和提升服务中权衡利弊，实现多目标共赢。
五、总结与展望
从研究视角、模型、求解算法三方面进行创新，建立带软时间窗的集送一体化低油耗配送线路模型，设计PSO算法得出车辆路径，利用模拟数据进行仿真。多车型、多配送中心和装箱约束是本文下一步研究的方向。（作者单位：福州大学经济与管理学院）
参考文献：
[1] Moritz Fleischmann，RoelofKuik，Rommert Dekker.Controlling inventories with stochastic item returns：A basic model[J].European Journal of Operational Research，2002（138）：63-75.
[2] TolgaBektas， Gilbert Laporte. The Pollution-Routing Problem[J]. Transportation Research Part B，2011（45）：1232-1250.
[3] Iori M. Metaheuristic algorithms for combinatorial optimization problems[D]. Bologna： University of Bologna， 2004.
在實际配送中，车辆在配送的同时也有回收需求，即集送一体化VRP。随机需求VRP是指客户位置确定但需求量不确定，仅知道其概率分布。随着能源价格上升，节能物流得到发展，要求减少车辆在行驶过程中所产生的燃油消耗。综合考虑节能车辆路径问题和随机取货需求的研究还未引起广泛关注。本文研究软时间窗约束下，取货需求服从泊松分布的集送一体化节能配送线路优化问题，以期增加企业收益并降低能耗。
二、问题模型
以单配送中心与多个客户点之间的物流配送网络为研究对象。同类型的一组车辆装载客户所需的货物从配送中心出发，采用巡回运输方式按客户点进行配送和集货服务，最终返回配送中心。各节点位置、客户点的配送需求量已知，车辆出发前固定揽收货物量已知。在满足约束条件下，以最低成本得出运输线路决策，同时多揽收货物。
（一）假设条件
使用的车辆数不超过配送中心限制；每个客户仅被访问一次；送货与集货同时进行，服务时间忽略；距离取欧氏距离。时间窗开放后，客户回收货物是一个随机过程。参考Fleischmana[1]等人文献，假设回收过程为服从泊松分布。揽收货物为标准件，重量和数量成线性关系。
（二）符号与参数说明
C1为单位车辆固定启用成本。C0为单位距离运输费用。Cf为单位油价。sij为点i和j之间的距离。K={k=1，2，3，…，m}为车辆集合。A={（i，j），i∈N，j∈N，i≠j}代表车场、客户点之间边的集合。[Ei，Li]为客户i的服务时间窗要求。pe、pl分别为配送车辆提前到达、延迟到达的单位时间惩罚成本。Capa为车辆最大载重量。Tj为配送车辆到达客户j的时刻。Tij为车辆在弧（i，j）的行驶时间。Vij为弧（i，j）的行驶速度，取随机整数。F为单位重量货物的收件费用。g为单位件数货物的重量。di为出发前i的配送需求重量。pi为出发前i已知的揽收货物重量。αij为与弧（i，j）有关的常数。β与车型有关，ω为空车重量。Qij为弧i，j是车辆的载重量。tr为燃油转油耗系数。
决策变量xijk==1第k辆车服务客户i后连续服务客户j=0否则
（三）模型建立
min f1=C1∑mk=1xijk+∑k∈K∑（i，j）∈Asij·xijk·C0（1）
min f2=∑i∈NPTi（2）
式（1）、（2）表示行车成本和时间惩罚成本。假设客户i货物收集件数服从参数为λi·△t的泊松分布，建立集货载件数最大化目标函数。
maxR=F·g·∑i∈N，i≠0（Ti-Ei）·λi
车辆在弧i，j上行驶产生的能量消耗采用如下公式[2]：
EGij=αijω+Qij+βv2ijsij
该公式计算得出车辆在弧i，j上产生的的能耗EGij，单位焦耳，转化为kWh。1L0号柴油可提供约9.32kWh能量，柴油发动机平均燃油率约为39%，由此能量消耗转化为燃油量，计算出油耗成本。
minf3=Cf∑k∈K∑i，j∈Atr·αijω+Qij+βν2ijsij·xijk
式（3）转化为maxR=-minR，对4个优化目标进行线性加和转化为新目标函数Z。
minZ=f1+f2-R+f3
∑mk=1∑ni=0xijk=1j∈V＼{0}
∑mk=1∑nj=0xijk=1i∈V＼{0}
∑i∈NXi0k=∑j∈NX0jk≤mk∈K
∑i∈S∑j∈Sxij≤S-1，≤S≤n-2， SN
PTi=maxpeLi-Ti，0，pl（Ti-Ei）i∈N
Tij=dijvij
Tj=Ti+Tij
∑ni=1∑nj=1dixijk≤Capak∈K
∑ni=1∑nj=1pi+gTi-Eiλixijk≤Capak∈K
djxijk+pi+gTi-Eiλixijk≤Qij≤Capa-dixijk
∑nj=1Q0j=∑nj=1dj
式（7）、（8）为客户点的访问唯一性约束；式（9）表示所有车辆从车场出发，配送完后返回配送中心；式（10）保证不产生任何子回路。式（11）表示车辆的时间惩罚成本；式（12）表示车辆从节点i到j的行驶时间；式（13）表示到达j的时间。式（15）表示出发时，正向配送需求重量约束；式（16）表示返回时，揽收货物重量约束；式（17）表示车辆在i，j弧上的载重约束；式（18）保证出发时装载货物总和满足客户需求。
三、模型求解
PSO算法在解决车辆路径问题上十分高效，贪心算法在处理约束条件时快速简便，本文设计基于贪心算法的PSO算法优化车辆行驶路线。首先生成车辆服务客户序列，其次引入贪心算法对不满足车约束的方案进行调整，最后返回优化路径。每个粒子位置的具体编码由两部分构成：X为车辆使用情况的K维向量，位置编码取0或1分别代表未选用和选用；Y为车辆行驶路线的K×N维矩阵，N为客户数。对调整后的客户序列计算粒子适应度值，对不满足约束条件的粒子适应度值施加惩罚值M。运行结束所得全局最优值gbest
选取测试算例[3]，节点坐标、客户需求量等来自经典算例。αij=0.0981，β=2.1，v是取[40，80]上的随机整数。车场坐标（40，40），客户数20，车辆数6，车辆自重2.7吨，最大载重量1.5吨。算法最大迭代次数200，种群规模100，加速系数c1=c2=2.05；粒子惯性权重w1=0.729。对算例重复仿真20次，统计最佳适应度值，见表1。
最优解对应的车辆总行驶成本4882元，燃油消耗成本378元，不满足软时间窗的惩罚成本259元。6辆车均被选用，行车路径为：车辆1：0-12-30-4-29-22-1-0；车辆2：0-7-18-3-0；车辆3：0-21-14-19-27-13-0；车辆4：0-28-8-11-0；车辆5：0-26-25-10-24-15-20-2-17-0；车辆6：0-16-5-23-9-6-0。
为验证优化效果，另设计不考虑动态集货数量和油耗费用的配送行驶方案并进行求解。在相同运行环境下，重复运行5次所得最优结果见表2。
根据上表可知，综合考虑集货需求和油耗两个因素后，配送成本上升，但集货收益增加，更好满足客户的集货需求，且几乎实现车辆满载，油耗费用降低。
综上所述，揽收货物需求、降低能耗的差异性，在一定程度上对物流配送线路均存在影响。节省油耗成本又增加集货收益的同时，往往又提升其他配送成本，而客户的满意率也受到影响。因此，物流企业根据实际情况制定决策方案时，需考虑如何在节约成本和提升服务中权衡利弊，实现多目标共赢。
五、总结与展望
从研究视角、模型、求解算法三方面进行创新，建立带软时间窗的集送一体化低油耗配送线路模型，设计PSO算法得出车辆路径，利用模拟数据进行仿真。多车型、多配送中心和装箱约束是本文下一步研究的方向。（作者单位：福州大学经济与管理学院）
参考文献：
[1] Moritz Fleischmann，RoelofKuik，Rommert Dekker.Controlling inventories with stochastic item returns：A basic model[J].European Journal of Operational Research，2002（138）：63-75.
[2] TolgaBektas， Gilbert Laporte. The Pollution-Routing Problem[J]. Transportation Research Part B，2011（45）：1232-1250.
[3] Iori M. Metaheuristic algorithms for combinatorial optimization problems[D]. Bologna： University of Bologna， 2004.