广东工业大学学报 ›› 2022, Vol. 39 ›› Issue (05): 61-67.doi: 10.12052/gdutxb.220067

• • 上一篇    下一篇

绿色车辆路径问题的改进拉格朗日松弛算法

徐林浩1, 钱斌1, 胡蓉1, 于乃康2   

  1. 1. 昆明理工大学 信息工程与自动化学院，云南 昆明 650500;
    2. 昆明理工大学 机电工程学院，云南 昆明 650500
  • 收稿日期:2022-04-01 发布日期:2022-07-18
  • 通信作者: 钱斌(1976–)，男，教授，博士，博士生导师，主要研究方向为智能优化调度理论与方法，E-mail：bin.qian@vip.163.com
  • 作者简介:徐林浩(1997–)，男，硕士研究生，主要研究方向为复杂系统智能优化
  • 基金资助:
    国家自然科学基金资助项目(62173169，61963022)；云南省基础研究重点资助项目(202201AS070030)

An Improved Lagrange Relaxation Algorithm for Green Vehicle Routing Problem

Xu Lin-hao1, Qian Bin1, Hu Rong1, Yu Nai-kang2   

  1. 1. School of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China;
    2. School of Mechanical and Electrical Engineering, Kunming University of Science and Technology, Kunming 650500, China
  • Received:2022-04-01 Published:2022-07-18

HTML

PDF (PC)

2357

摘要： 针对绿色带容量的车辆路径问题(Green Capacitated Vehicle Routing Problem, GCVRP)，建立了以最小化总运费为优化目标的混合整数规划(Mixed Integer Programming,MIP)模型，并提出一种改进拉格朗日松弛算法(Improved Lagrange Relaxation Algorithm, ILRA)进行求解。首先，通过拉格朗日松弛技术得到原问题的对偶问题，并运用次梯度法求解对偶问题获得原问题的下界；然后针对下界设计修复算法和邻域搜索算法获得原问题的上界，进而更新乘子迭代求解；最后进行仿真实验，实验结果表明：在相同实验环境下对19个不同规模算例进行10次测试，ILRA求取MIP的上下界平均间隙为7.61%，而Gurobi求解器求取的平均间隙为15.47%。可见，相较于Gurobi求解器，ILRA能够高效获得GCVRP的高质量解。

关键词: 绿色带容量的车辆路径问题, 混合整数规划, 改进拉格朗日松弛, 下界

Abstract: To address the green capacitated vehicle routing problem (GCVRP), a mixed integer programming (MIP) model is established to minimize the total freight cost, and an improved Lagrange relaxation algorithm (ILRA) is proposed to solve the problem. Firstly, the dual problem of the original problem is obtained by Lagrange relaxation technique, and the lower bound of the original problem is obtained by solving the dual problem by subgradient method; Secondly a repair algorithm and a neighborhood search algorithm are designed to obtain the upper bound of the original problem, and then update the multiplier iterative solution; Finally, a simulation experiment is carried out. The experimental results show that 10 tests are carried out on 19 cases of different scales under the same experimental environment. The average gap between the upper and lower bounds of MIP obtained by ILRA is 7.61%, while the average gap obtained by Gurobi solver is 15.47%. Therefore, compared with Gurobi solver, ILRA can obtain high-quality solutions of GCVRP efficiently.

Key words: green capacitated vehicle routing problem, mixed integer programming, improved Lagrange relaxation, lower bound

中图分类号: 

  • TP391.9
[1] DANTZIG G B, RAMSER J H. The truck dispatching problem [J]. Management Science, 1959, 6(1): 80-91.
[2] BENSLIMANE M T, BENADADA Y. Ant colony algorithm for the multi-depot vehicle routing problem in large quantities by a heterogeneous fleet of vehicles [J]. Information Systems & Operational Research, 2013, 51(1): 31-40.
[3] SINGH V, GANAPATHY L, PUNDIR A K. An improved genetic algorithm for solving multi depot vehicle routing problems [J]. International Journal of Information Systems and Supply Chain Management, 2019, 12(4): 1-26.
[4] 朱晓锋, 蔡延光. 带时间窗的模糊需求多类型车辆路径问题禁忌搜索算法[J]. 广东工业大学学报, 2008, 25(3): 55-60.
ZHU X F, CAI Y G. Research on multi-vehicle scheduling problems with fuzzy demand and time windows [J]. Journal of Guangdong University of Technology, 2008, 25(3): 55-60.
[5] SINGH V P, K SHARMA, CHAKRABORTY D. A branch and bound based solution method for solving vehicle routing problem with fuzzy stochastic demands [J]. Sadhana, 2021, 46(4): 1-17.
[6] LYSGAARD J, W?HLK S. A branch-and-cut-and-price algorithm for the mixed capacitated general routing problem [J]. European Journal of Operational Research, 2014, 236(3): 800-810.
[7] MAJID S K, MICHEL G, OLA J, et al. An exact algorithm to solve the vehicle routing problem with stochastic demands under an optimal restocking policy [J]. European Journal of Operational Research, 2018, 273(1): 175-189.
[8] CHRISTIANSEN C H, LYSGAARD J. A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands [J]. Operations Research Letters, 2009, 35(6): 773-781.
[9] ANDELMIN J, BARTOLINI E. An exact algorithm for the green vehicle routing problem [J]. Transportation Science, 2017, 51(4): 1288-1303.
[10] DABIA S, DEMIR E, WOENSEL T V. An exact approach for a variant of the pollution-routing problem [J]. Transportation Science, 2017, 51(2): 607-628.
[11] BOUZID M C, HADDADENE H A, SALHI S. An integration of Lagrangian split and VNS: the case of the capacitated vehicle routing problem[J]. Computers & Operations Research, 2017, 78: 513-525.
[12] ÇAĞRI, KOÇ, KARAOGLAN I. The green vehicle routing problem: a heuristic based exact solution approach[J]. Applied Soft Computing, 2016, 39: 154-164.
[13] QIU Y, QIAO J, PARDALOS P M. A branch-and-price algorithm for production routing problems with carbon cap-and-trade[J]. Omega, 2017, 68: 49-61.
[14] DEMIR E, BEKTAS T, LAPORTE G. An adaptive large neighborhood search heuristic for the pollution-routing problem [J]. European Journal of Operational Research, 2012, 232(2): 346-359.
[15] FRANCESCHETTI A, HONHON D, WOENSEL T V, et al. The time-dependent pollution-routing problem [J]. Transportation Research Part B, 2013, 56(56): 265-293.
[16] 葛显龙, 苗国庆, 谭柏川. 开放式污染路径问题优化建模与算法研究[J]. 工业工程与管理, 2015, 20(4): 46-53.
GE X L, MIAO G Q, TAN B C, Research on optimization modeling and algorithm for open pollution routing problem[J]. Industrial Engineering and Management, 2015, 20(4): 46-53.
[1] 杨铀； 薛秀谦； 段滋明； . 圈对完全图Ramsey数r（C4,Kn）的3个新下界[J]. 广东工业大学学报, 2003, 20(1): 86-88.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2017 《广东工业大学学报》编辑部
地址：广州市东风东路729号广东工业大学 邮编：510090
电话：020-37626653,020-37626139,020-37626396
邮箱：xbzrb@gdut.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发