需求不确定的车辆路径鲁棒优化模型
管峰++钟铭++韦达
摘要：基于顾客需求不确定可能造成确定性条件下最优路径的不可行性，采用鲁棒优化模型解决需求不确定的、有容量限制的车辆路径问题，分析并证明了需求分别属于凸集合和盒子集合两种有界集合下的鲁棒优化模型.建立偏差系数比较鲁棒优化模型和确定性模型的目标函数值，通过实例说明，虽然鲁棒优化模型的最优目标函数值高于确定性模型的，但是能有效保证路径在需求波动下的可行性，模型可行，
关键词：需求不确定；车辆路径；鲁棒优化；偏差系数
中图分类号：U492.22；F252.14
文献标志码：A
0 引言
规划车辆路径时主要考虑的因素之一是顾客运输需求量，而实际的顾客运输需求量由于受各种因素的影响具有不确定性，因此有必要考虑在需求不确定性条件下的车辆路径优化.
在现有文献中，对需求不确定的车辆路径问题的处理方法有随机规划和模糊规划等，文献[1-3]将需求作为随机变量，建立随机规划模型优化车辆路径；文献[4-7]假设顾客需求是模糊变量，提出模糊规划模型解决车辆路径问题，但事实上，用这些方法得到的最优路径很可能对需求波动具有较强敏感性，即当需求发生较小波动时，利用随机规划或模糊规划得到的最优路径很有可能已不是最优解，甚至可能因为路径上总需求量超过车辆最大载重量而变为非可行解，因此，需要获得一个对需求波动免疫的最优解.此最优解要满足的条件是：对所有的需求变动都保持可行解，同时使目标值最优，基于此，本文采用鲁棒优化方法处理上述问题，利用鲁棒优化处理需求不确定条件下车辆路径问题的明显优势是可以求得一个对需求波动不敏感、对不确定免疫的最优解，即：对于可能出现的所有情况，约束条件均能满足，并且使得最坏情况下目标函数的值最优，近年来，鲁棒优化经过BEN-TAL等、BERTSIMAS等的深入研究已形成体系，并且在诸如航线网络、城市交通、应急救援等领域得到广泛应用，但是，用鲁棒优化模型得到的目标函数值比确定性条件下的目标函数值大.因此，需要引入偏差系数进一步评价鲁棒解的优劣.
本文采用鲁棒优化方法建立需求不确定的、有容量限制的车辆路径鲁棒优化模型，使得到的鲁棒路径在最坏情形下也能满足容量限制并保证成本最小，然后通过偏差系数比较鲁棒优化目标函数值与确定性需求的差异.
1 车辆路径鲁棒优化模型
1.1 需求不确定的表示方法
1.2 车辆路径鲁棒优化模型
车辆路径鲁棒优化模型是以需求确定的、有容量限制的车辆鲁棒优化模型为基础的，因此先要建立确定性模型.假设：物流配送中心最多可用K辆车进行配送，k=l，2，…，K；每辆车车型相同且每辆车的最大装载能力为Q；第i个顾客的需求为di，每个客户只能用一辆车服务；客户与客户之间的运输距离为cij.令集合V= VdU{0}表示所有顾客需求点和物流配送中心的集合，其中Vd={1，2，…，n}为顾客需求点集合，0为物流配送中心.
决策变量：yki为0-1变量，发货点i的任务由车k完成时为l，否则为0；Xijk为0-1变量，车k从点i行驶到点j时为1，否则为0.
确定性的车辆优化调度数学模型如下：
通过分析模型可知，不确定的需求量di只在约束条件（2）中出现，其余并未出现，因此，只需研究约束条件（2），然后建立相应的鲁棒优化模型，
定义1在凸集合Z1条件下，代替约束条件（2）的鲁棒对应方程为
2 实例分析
选取徐杰等的实例，将问题描述为一个有7个顾客需求点的车辆路径问题.各顾客需求点的坐标（x，y）及需求见表1，配送中心车辆数最多为5.
车辆路径问题通常采用遗传算法、粒子群算法、禁忌搜索法等求解，鉴于本次数据规模较小，可采用Ling0 11直接求解，确定需求条件下车辆最短距离为217.814.最优路径3条，分别为：路径R1，0-1-0，路径总运量Q（R1）=0.89；路径R2，0-7-6-0，Q（R2）=0.98；路径R3，0-2-3-4-5-0，Q（R3）=0.96.具体路径见图1.
由于需求受外部环境的影响较大，不可能是一个稳定值，现假设顾客6的营销情况良好，想要增加5%的需求，此时，若仍按照确定性条件下优化的路径R2运营，可以发现需求变化后的路径总运量Q（R2）=1.01，超过汽车最大载重量1，因此路径2是不可行路径，即需求变动微小时可直接导致解不可行.为说明需求波动可能造成确定性条件下最优路径的非可行性，求出满足所有需求可能性的鲁棒解是有重要意义的，
对于顾客需求的变化，首先假设所有需求点的需求波动分别为-1%，1%，-3%，3%.以需求点1为例说明：d10=0.89，d11=-0.89×10-2，d12=0.89xl0-2， d13=-0.267×10-1，d14=0.267×10-1，用Qmax（R）表示路径R上最坏情况下的需求总运量.在集合Z1条件下，利用鲁棒优化模型求解得到最短距离为238.905，最优路径4条，分别为：路径R1，0-1-0，Qmax（R1）=0.9167；路径R2，0-6-0，Qmax（R2）=0.4223；路径R3，0-7-0，Qmax（R3）=0.6601；路径R4，0-2-3-4-5-0，Qmax（R4）=1.0.
需求波动后，如果继续沿确定性条件下的路径R2运行，可能会导致最坏情况下路径总运量超过汽车最大运载能力的8%，因此需要重新安排一辆车，而采用鲁棒优化模型后，不管需求如何变动，4条路径仍然保持可行.
在集合Z2条件下，利用鲁棒优化模型求解得到最短距离为311.4130，最优路径4条（见图1），分别为：路径R1，0-1-0，Qmax（R1）=0.9612；路径R2，0-2-6-0，Qmax（R2）=0.5940；路径R3，0-7-0，Qmax（R3）=0.6436；路径R4，O-3-4-5-0，Qmax（R4）=0.7732.这4条路径在需求波动最大时仍能满足载重约束条件，
两种鲁棒优化模型产生的最优路径都能保证满足所有需求波动情形，不会出现路径上顾客需求量超过汽车最大运载能力的情况，但这是以牺牲目标函数的值为代价的，本文引入偏差系数P表示为满足任意需求波动下的路径可行而增加的目标函数的百分比，在集合Z1条件下，P为9.7%，在集合Z2条件下P为42.9%，比集合Z1条件下高出33.2%.因此，需要在实际应用中考虑不确定量所属有界集合类型，若偏差系数过大则要谨慎使用鲁棒优化方法，若偏差系数较小，则鲁棒优化方法具有较大的优越性.
3 结论
针对在需求不确定时采用随机规划和模糊规划方法得到的最优路径可能对需求波动敏感的情况，提出利用鲁棒优化模型解决有容量限制的车辆路径问题.研究发现，鲁棒优化模型可以很好地规避需求波动所导致的最优路径不可行性问题.
在实际问题中，除顾客需求可能是不确定的外，车辆的运行时间等因素也可能是不确定的.因此，考虑提高车辆准班率，建立具有鲁棒性的车辆调度模型将是进一步的研究方向.
参考文献：
[1]BERTSIMAS D J.A vehicle routing problem with stochastic demand[J].Operations Research，1992，40（3）：574-585.
[2]LAPORTE G，LOUVEAUX F V，van HAMME L An integer L-shaped algorithm for the capacitated vehicle routing problem with stochastic de- mands[J].Operations Research，2002，50（3）：415-423.
[3]樊建华，王秀峰.随机需求多车辆路径问题的重优化算法[J].南开大学学报（自然科学版），2008，41（2）：103-107.
[4]张建勇，李军.模糊车辆路径问题的一种混合遗传算法[J].管理工程学报，2005，19（2）：23-26.
[5]张建勇，郭耀煌，李军.模糊需求信息条件下的车辆路径问题研究[J].系统工程学报，2004，19（1）：74-78.
[6]崔广彬，李一军.模糊需求下物流系统CLRIP问题研究[J]。控制与决策，2007，22（9）：1000-1004.
[7]甘勤涛，阳平华，童钟灵.模糊需求车辆路径问题的禁忌搜索算法研究[J].长春理工大学学报，2006，29（1）：84-85.
摘要：基于顾客需求不确定可能造成确定性条件下最优路径的不可行性，采用鲁棒优化模型解决需求不确定的、有容量限制的车辆路径问题，分析并证明了需求分别属于凸集合和盒子集合两种有界集合下的鲁棒优化模型.建立偏差系数比较鲁棒优化模型和确定性模型的目标函数值，通过实例说明，虽然鲁棒优化模型的最优目标函数值高于确定性模型的，但是能有效保证路径在需求波动下的可行性，模型可行，
关键词：需求不确定；车辆路径；鲁棒优化；偏差系数
中图分类号：U492.22；F252.14
文献标志码：A
0 引言
规划车辆路径时主要考虑的因素之一是顾客运输需求量，而实际的顾客运输需求量由于受各种因素的影响具有不确定性，因此有必要考虑在需求不确定性条件下的车辆路径优化.
在现有文献中，对需求不确定的车辆路径问题的处理方法有随机规划和模糊规划等，文献[1-3]将需求作为随机变量，建立随机规划模型优化车辆路径；文献[4-7]假设顾客需求是模糊变量，提出模糊规划模型解决车辆路径问题，但事实上，用这些方法得到的最优路径很可能对需求波动具有较强敏感性，即当需求发生较小波动时，利用随机规划或模糊规划得到的最优路径很有可能已不是最优解，甚至可能因为路径上总需求量超过车辆最大载重量而变为非可行解，因此，需要获得一个对需求波动免疫的最优解.此最优解要满足的条件是：对所有的需求变动都保持可行解，同时使目标值最优，基于此，本文采用鲁棒优化方法处理上述问题，利用鲁棒优化处理需求不确定条件下车辆路径问题的明显优势是可以求得一个对需求波动不敏感、对不确定免疫的最优解，即：对于可能出现的所有情况，约束条件均能满足，并且使得最坏情况下目标函数的值最优，近年来，鲁棒优化经过BEN-TAL等、BERTSIMAS等的深入研究已形成体系，并且在诸如航线网络、城市交通、应急救援等领域得到广泛应用，但是，用鲁棒优化模型得到的目标函数值比确定性条件下的目标函数值大.因此，需要引入偏差系数进一步评价鲁棒解的优劣.
本文采用鲁棒优化方法建立需求不确定的、有容量限制的车辆路径鲁棒优化模型，使得到的鲁棒路径在最坏情形下也能满足容量限制并保证成本最小，然后通过偏差系数比较鲁棒优化目标函数值与确定性需求的差异.
1 车辆路径鲁棒优化模型
1.1 需求不确定的表示方法
1.2 车辆路径鲁棒优化模型
车辆路径鲁棒优化模型是以需求确定的、有容量限制的车辆鲁棒优化模型为基础的，因此先要建立确定性模型.假设：物流配送中心最多可用K辆车进行配送，k=l，2，…，K；每辆车车型相同且每辆车的最大装载能力为Q；第i个顾客的需求为di，每个客户只能用一辆车服务；客户与客户之间的运输距离为cij.令集合V= VdU{0}表示所有顾客需求点和物流配送中心的集合，其中Vd={1，2，…，n}为顾客需求点集合，0为物流配送中心.
决策变量：yki为0-1变量，发货点i的任务由车k完成时为l，否则为0；Xijk为0-1变量，车k从点i行驶到点j时为1，否则为0.
确定性的车辆优化调度数学模型如下：
通过分析模型可知，不确定的需求量di只在约束条件（2）中出现，其余并未出现，因此，只需研究约束条件（2），然后建立相应的鲁棒优化模型，
定义1在凸集合Z1条件下，代替约束条件（2）的鲁棒对应方程为
2 实例分析
选取徐杰等的实例，将问题描述为一个有7个顾客需求点的车辆路径问题.各顾客需求点的坐标（x，y）及需求见表1，配送中心车辆数最多为5.
车辆路径问题通常采用遗传算法、粒子群算法、禁忌搜索法等求解，鉴于本次数据规模较小，可采用Ling0 11直接求解，确定需求条件下车辆最短距离为217.814.最优路径3条，分别为：路径R1，0-1-0，路径总运量Q（R1）=0.89；路径R2，0-7-6-0，Q（R2）=0.98；路径R3，0-2-3-4-5-0，Q（R3）=0.96.具体路径见图1.
由于需求受外部环境的影响较大，不可能是一个稳定值，现假设顾客6的营销情况良好，想要增加5%的需求，此时，若仍按照确定性条件下优化的路径R2运营，可以发现需求变化后的路径总运量Q（R2）=1.01，超过汽车最大载重量1，因此路径2是不可行路径，即需求变动微小时可直接导致解不可行.为说明需求波动可能造成确定性条件下最优路径的非可行性，求出满足所有需求可能性的鲁棒解是有重要意义的，
对于顾客需求的变化，首先假设所有需求点的需求波动分别为-1%，1%，-3%，3%.以需求点1为例说明：d10=0.89，d11=-0.89×10-2，d12=0.89xl0-2， d13=-0.267×10-1，d14=0.267×10-1，用Qmax（R）表示路径R上最坏情况下的需求总运量.在集合Z1条件下，利用鲁棒优化模型求解得到最短距离为238.905，最优路径4条，分别为：路径R1，0-1-0，Qmax（R1）=0.9167；路径R2，0-6-0，Qmax（R2）=0.4223；路径R3，0-7-0，Qmax（R3）=0.6601；路径R4，0-2-3-4-5-0，Qmax（R4）=1.0.
需求波动后，如果继续沿确定性条件下的路径R2运行，可能会导致最坏情况下路径总运量超过汽车最大运载能力的8%，因此需要重新安排一辆车，而采用鲁棒优化模型后，不管需求如何变动，4条路径仍然保持可行.
在集合Z2条件下，利用鲁棒优化模型求解得到最短距离为311.4130，最优路径4条（见图1），分别为：路径R1，0-1-0，Qmax（R1）=0.9612；路径R2，0-2-6-0，Qmax（R2）=0.5940；路径R3，0-7-0，Qmax（R3）=0.6436；路径R4，O-3-4-5-0，Qmax（R4）=0.7732.这4条路径在需求波动最大时仍能满足载重约束条件，
两种鲁棒优化模型产生的最优路径都能保证满足所有需求波动情形，不会出现路径上顾客需求量超过汽车最大运载能力的情况，但这是以牺牲目标函数的值为代价的，本文引入偏差系数P表示为满足任意需求波动下的路径可行而增加的目标函数的百分比，在集合Z1条件下，P为9.7%，在集合Z2条件下P为42.9%，比集合Z1条件下高出33.2%.因此，需要在实际应用中考虑不确定量所属有界集合类型，若偏差系数过大则要谨慎使用鲁棒优化方法，若偏差系数较小，则鲁棒优化方法具有较大的优越性.
3 结论
针对在需求不确定时采用随机规划和模糊规划方法得到的最优路径可能对需求波动敏感的情况，提出利用鲁棒优化模型解决有容量限制的车辆路径问题.研究发现，鲁棒优化模型可以很好地规避需求波动所导致的最优路径不可行性问题.
在实际问题中，除顾客需求可能是不确定的外，车辆的运行时间等因素也可能是不确定的.因此，考虑提高车辆准班率，建立具有鲁棒性的车辆调度模型将是进一步的研究方向.
参考文献：
[1]BERTSIMAS D J.A vehicle routing problem with stochastic demand[J].Operations Research，1992，40（3）：574-585.
[2]LAPORTE G，LOUVEAUX F V，van HAMME L An integer L-shaped algorithm for the capacitated vehicle routing problem with stochastic de- mands[J].Operations Research，2002，50（3）：415-423.
[3]樊建华，王秀峰.随机需求多车辆路径问题的重优化算法[J].南开大学学报（自然科学版），2008，41（2）：103-107.
[4]张建勇，李军.模糊车辆路径问题的一种混合遗传算法[J].管理工程学报，2005，19（2）：23-26.
[5]张建勇，郭耀煌，李军.模糊需求信息条件下的车辆路径问题研究[J].系统工程学报，2004，19（1）：74-78.
[6]崔广彬，李一军.模糊需求下物流系统CLRIP问题研究[J]。控制与决策，2007，22（9）：1000-1004.
[7]甘勤涛，阳平华，童钟灵.模糊需求车辆路径问题的禁忌搜索算法研究[J].长春理工大学学报，2006，29（1）：84-85.
