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

徐林浩; 钱斌; 胡蓉; 于乃康

doi:10.12052/gdutxb.220067

欢迎来到能源电力期刊网！

English Version 期刊登录

您当前的位置：

首页 >

文章列表页 >

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

更新时间：2026-05-27

- 绿色车辆路径问题的改进拉格朗日松弛算法
- An Improved Lagrange Relaxation Algorithm for Green Vehicle Routing Problem
- 广东工业大学学报 2022年39卷第5期页码：61-67
- 作者机构：
  
  1. 昆明理工大学信息工程与自动化学院,云南,昆明,650500
  2. 昆明理工大学机电工程学院,云南,昆明,650500
- 作者简介：
  
  徐林浩(1997–)，男，硕士研究生，主要研究方向为复杂系统智能优化
  钱斌(1976–)，男，教授，博士，博士生导师，主要研究方向为智能优化调度理论与方法，E-mail：bin.qian@vip.163.com
- 基金信息：
  
  国家自然科学基金资助项目(62173169，61963022);云南省基础研究重点资助项目(202201AS070030)
- DOI：10.12052/gdutxb.220067
  中图分类号： TP391.9
- 纸质出版：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.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

储能变流器电能质量治理策略研究

SCA-YOLO: 基于可变形卷积与上下文感知注意力的实时目标检测

具守恒量波动方程的循环双子网物理信息神经网络

面向灾后救援的多无人机通感算一体化资源分配优化方法

基于路况参数的混合动力机车能量管理策略研究