An Improved Lagrange Relaxation Algorithm for Green Vehicle Routing Problem

Xu Lin-hao; Qian Bin; Hu Rong; Yu Nai-kang

doi:10.12052/gdutxb.220067

English Version Journal Login

您当前的位置：

首页 >

文章列表页 >

An Improved Lagrange Relaxation Algorithm for Green Vehicle Routing Problem

更新时间：2026-05-27

- An Improved Lagrange Relaxation Algorithm for Green Vehicle Routing Problem
- Vol. 39, Issue 5, Pages: 61-67(2022)
- 作者机构：
  
  1. 昆明理工大学信息工程与自动化学院,云南,昆明,650500
  2. 昆明理工大学机电工程学院,云南,昆明,650500
- 作者简介：
- 基金信息：
- DOI：10.12052/gdutxb.220067
  CLC： TP391.9
- Published：2022
- 稿件说明：
移动端阅览
徐林浩, 钱斌, 胡蓉, 于乃康. 绿色车辆路径问题的改进拉格朗日松弛算法[J]. 广东工业大学学报, 2022, 39(5): 61-67.

Xu Lin-hao, Qian Bin, Hu Rong, et al. An Improved Lagrange Relaxation Algorithm for Green Vehicle Routing Problem[J]. 2022, 39(5): 61-67.
徐林浩, 钱斌, 胡蓉, 于乃康. 绿色车辆路径问题的改进拉格朗日松弛算法[J]. 广东工业大学学报, 2022, 39(5): 61-67. DOI： 10.12052/gdutxb.220067.

Xu Lin-hao, Qian Bin, Hu Rong, et al. An Improved Lagrange Relaxation Algorithm for Green Vehicle Routing Problem[J]. 2022, 39(5): 61-67. DOI： 10.12052/gdutxb.220067.

摘要

针对绿色带容量的车辆路径问题(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.

关键词

Keywords

references

DANTZIG G B, RAMSER J H. The truck dispatching problem [J]. Management Science, 1959, 6(1): 80-91.

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.

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.

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.

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.

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.

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.

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.

ANDELMIN J, BARTOLINI E. An exact algorithm for the green vehicle routing problem [J]. Transportation Science, 2017, 51(4): 1288-1303.

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.

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.

ARI, KO, KARAOGLAN I. The green vehicle routing problem: a heuristic based exact solution approach[J]. Applied Soft Computing, 2016, 39: 154-164.

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.

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.

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.

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.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

An Optimal Operation Strategy for Community Microgrid Alliances Considering Power Exchange under Multi-package Shared Energy Storage Model

Robust Design for Artificial Noise-assisted UAV Terahertz Secure Communication

Research on Foreign Object Detection in Power Transmission Lines Based on the AAGV-YOLOX Model

A Study of Power Quality Regulation Strategies of Energy Storage Converters

Bimodal Iterative Cross-attention Fusion Ensemble Framework

Related Author

No data

Related Institution

No data

AI问答

⁰