Journal of Guangdong University of Technology ›› 2022, Vol. 39 ›› Issue (05): 61-67.doi: 10.12052/gdutxb.220067

Previous Articles     Next Articles

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

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

CLC Number: 

  • 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] Li Jin-fang, Wei Guang-yang, He Han-wu, Cai Jia-hong, Chen Ji-rong. An Algorithm for Simulation of Gingival Tissue Deformation Based on Mass-Spring Model [J]. Journal of Guangdong University of Technology, 2020, 37(03): 49-54.
[2] Cai Nian, Li Fei-yang, Chen Wen-jie, Chen Wei-jian. Smart Growth Modeling and Prediction Based on Principle Component Analysis and Support Vector Regression [J]. Journal of Guangdong University of Technology, 2017, 34(05): 29-33.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright © 2017 Journal of Guangdong University of Technology
Add：729 East Dongfeng RD., Guangzhou PRC. Postcode: 510090
Tel：020-37626653,020-37626139,020-37626396
Email：xbzrb@gdut.edu.cn
Supported:Beijing Magtech