需求不确定的车辆路径鲁棒优化模型

-精选财经经济类资料- -最新财经经济资料-感谢阅读- 1 需求不确定的车辆路径鲁棒优化模 型 摘要：基于顾客需求不确定可能 造成确定性条件下最优路径的不可行性， 采用鲁棒优化模型解决需求不确定的、 有容量限制的车辆路径问题，分析并证 明了需求分别属于凸集合和盒子集合两 种有界集合下的鲁棒优化模型.建立偏差 系数比较鲁棒优化模型和确定性模型的 目标函数值，通过实例说明，虽然鲁棒 优化模型的最优目标函数值高于确定性 模型的，但是能有效保证路径在需求波 动下的可行性，模型可行， 中国论文网 /4/view-12760082.htm 关键词：需求不确定；车辆路径； 鲁棒优化；偏差系数 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 2 中图分类号：U492.22；F252.14 文献标志码：A 0 引言 规划车辆路径时主要考虑的因素 之一是顾客运输需求量，而实际的顾客 运输需求量由于受各种因素的影响具有 不确定性，因此有必要考虑在需求不确 定性条件下的车辆路径优化. 在现有文献中，对需求不确定的 车辆路径问题的处理方法有随机规划和 模糊规划等，文献1-3将需求作为随机 变量，建立随机规划模型优化车辆路径； 文献4-7 假设顾客需求是模糊变量，提 出模糊规划模型解决车辆路径问题，但 事实上，用这些方法得到的最优路径很 可能对需求波动具有较强敏感性，即当 需求发生较小波动时，利用随机规划或 模糊规划得到的最优路径很有可能已不 是最优解，甚至可能因为路径上总需求 量超过车辆最大载重量而变为非可行解， 因此，需要获得一个对需求波动免疫的 最优解.此最优解要满足的条件是：对所 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 3 有的需求变动都保持可行解，同时使目 标值最优，基于此，本文采用鲁棒优化 方法处理上述问题，利用鲁棒优化处理 需求不确定条件下车辆路径问题的明显 优势是可以求得一个对需求波动不敏感、 对不确定免疫的最优解，即：对于可能 出现的所有情况，约束条件均能满足， 并且使得最坏情况下目标函数的值最优， 近年来，鲁棒优化经过 BEN-TAL 等、 BERTSIMAS 等的深入研究已形成体系， 并且在诸如航线网络、城市交通、应急 救援等领域得到广泛应用，但是，用鲁 棒优化模型得到的目标函数值比确定性 条件下的目标函数值大.因此，需要引入 偏差系数进一步评价鲁棒解的优劣. 本文采用鲁棒优化方法建立需求 不确定的、有容量限制的车辆路径鲁棒 优化模型，使得到的鲁棒路径在最坏情 形下也能满足容量限制并保证成本最小， 然后通过偏差系数比较鲁棒优化目标函 数值与确定性需求的差异. 1 车辆路径鲁棒优化模型 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 4 1.1 需求不确定的表示方法 1.2 车辆路径鲁棒优化模型 车辆路径鲁棒优化模型是以需求 确定的、有容量限制的车辆鲁棒优化模 型为基础的，因此先要建立确定性模型. 假设：物流配送中心最多可用 K 辆车进 行配送，k=l，2，K；每辆车车型 相同且每辆车的最大装载能力为 Q；第 i 个顾客的需求为 di，每个客户只能用 一辆车服务；客户与客户之间的运输距 离为 cij.令集合 V= VdU0表示所有顾 客需求点和物流配送中心的集合，其中 Vd=1，2，n为顾客需求点集合， 0 为物流配送中心. 决策变量：yki 为 0-1 变量，发 货点 i 的任务由车 k 完成时为 l，否则 为 0；Xijk 为 0-1 变量，车 k 从点 i 行 驶到点 j 时为 1，否则为 0. 确定性的车辆优化调度数学模型 如下： 通过分析模型可知，不确定的需 求量 di 只在约束条件（2）中出现，其 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 5 余并未出现，因此，只需研究约束条件 （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%的需求， 此时，若仍按照确定性条件下优化的路 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 6 径 R2 运营，可以发现需求变化后的路 径总运量 Q（R2）=1.01，超过汽车最 大载重量 1，因此路径 2 是不可行路径， 即需求变动微小时可直接导致解不可行. 为说明需求波动可能造成确定性条件下 最优路径的非可行性，求出满足所有需 求可能性的鲁棒解是有重要意义的， 对于顾客需求的变化，首先假设 所有需求点的需求波动分别为- 1%，1%，-3%，3%.以需求点 1 为例说 明：d10=0.89，d11=-0.8910- 2，d12=0.89xl0-2， d13=-0.26710- 1，d14=0.26710-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. 需求波动后，如果继续沿确定性条件下 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 7 的路径 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 条件 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 8 下 P 为 42.9%，比集合 Z1 条件下高出 33.2%.因此，需要在实际应用中考虑不 确定量所属有界集合类型，若偏差系数 过大则要谨慎使用鲁棒优化方法，若偏 差系数较小，则鲁棒优化方法具有较大 的优越性. 3 结论 针对在需求不确定时采用随机规 划和模糊规划方法得到的最优路径可能 对需求波动敏感的情况，提出利用鲁棒 优化模型解决