| 引用本文: | 孙亮,王冰,郭栋,等.求解不确定型车辆路径问题的弱鲁棒优化方法.[J].国防科技大学学报,2020,42(3):30-38.[点击复制] |
| SUN Liang,WANG Bing,GUO Dong,et al.Light robust optimization approach for vehicle routing problem under uncertainty[J].Journal of National University of Defense Technology,2020,42(3):30-38[点击复制] |
|
| |
|
|
| 本文已被：浏览 7126次 下载 5098次 |
| 求解不确定型车辆路径问题的弱鲁棒优化方法 |
| 孙亮1,2,王冰1,郭栋1,徐艺1 |
|
(1. 山东理工大学 交通与车辆工程学院, 山东 淄博 255049;2. 上海大学 机电工程与自动化学院, 上海 200072)
|
| 摘要: |
| 为降低鲁棒优化模型最优解的保守性,以最小化违约车辆数和总惩罚成本为目标,建立针对旅行时间不确定的开放式车辆路径问题的弱鲁棒优化模型。对于不确定数据集的每个取值,该模型的最优解可以使其目标函数值始终不超过某数值,进而改善最优解的保守性。为提高启发式算法发现最优解的概率,提出一种自设计遗传算法对模型进行求解,其主要思想是利用粒子群算法搜索出可使遗传算法预期产生最好解的算法要素,并将其进行组合,从而产生新的遗传算法。采用新产生的遗传算法对模型继续求解,输出最好解。计算结果表明:与以往的鲁棒优化方法相比,弱鲁棒优化方法的最优解的保守性显著降低。 |
| 关键词: 鲁棒优化 超启发式算法 遗传算法 车辆路径问题 |
| DOI：10.11887/j.cn.202003005 |
| 投稿日期：2018-12-27 |
| 基金项目:国家自然科学基金资助项目(51508315)；中国博士后面上基金资助项目(2018M642684)；山东省自然科学基金资助项目(ZR2018PEE016) |
|
| Light robust optimization approach for vehicle routing problem under uncertainty |
| SUN Liang1,2, WANG Bing1, GUO Dong1, XU Yi1 |
|
(1. School of Transportation and Vehicle Engineering, Shandong University of Technology, Zibo 255049, China;2. School of Mechatronic Engineering and Automation, Shanghai University, Shanghai 200072, China)
|
| Abstract: |
| Aiming to reduce conservatism of the optimal solution with regard to robust optimization model, a light robust optimization approach was proposed to solve the open vehicle routing problem with travel time uncertainty. This approach yields routes that minimize the weighted sum of the number of defaulted vehicles and the total penalty cost. For each realizations of the uncertain data set, the optimal solution of the approach can ensure that its optimal value never exceeds a certain value, thus improving the conservatism of the optimal solution. To improve the probability of finding the optimal solution, the automatic design of genetic algorithms was proposed to solve the model. Its main idea is to use the particle swarm optimization algorithm to search components of genetic algorithm which can expectedly enable the genetic algorithm to generate the optimal solution and then to combine these components to generate a new genetic algorithm to solve the model. The new genetic algorithm was used to solve the model continuously and give rise to a new optimal solution. Calculation results show that the conservatism of the optimal solution solved by the proposed light robust optimization approach is significantly reduced comparing with the past robust optimization method. |
| Keywords: robust optimization hyper-heuristic algorithm genetic algorithm vehicle routing problem |
|
|
|
|
|
