An Exact Column Generation-Based Algorithm for Bi-objective Vehicle Routing Problems

被引：4
作者：
Glize, Estele [1 ]
Jozefowiez, Nicolas [2 ]
Ngueveu, Sandra Ulrich [1 ]
机构：
[1] INP Toulouse, CNRS, LAAS, INSA, Toulouse, France
[2] Univ Lorraine, LCOMS, Metz, France
来源：
COMBINATORIAL OPTIMIZATION, ISCO 2018 | 2018年 / 10856卷
关键词：
Combinatorial MOP; Vehicle routing problem; Exact method; Column generation;
D O I：
10.1007/978-3-319-96151-4_18
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
We propose a new exact method for bi-objective vehicle routing problems where edges are associated with two costs. The method generates the minimum complete Pareto front of the problem by combining the scalarization of the objective function and the column generation technique. The aggregated objective allows to apply the exact algorithm for the mono-objective vehicle routing problem of Baldacci et al. (2008). The algorithm is applied to a bi-objective VRP with time-windows. Computational results are compared with a classical bi-objective technique. The results show the pertinence of the new method, especially for clustered instances.
引用
收藏
页码：208 / 218
页数：11
相关论文
共 50 条
  • [21] A Bi-Objective Column Generation Approach for Real-World Rolling Stock Circulation Planning Problems
    Paeprer, Paul
    Neufeld, Janis S.
    Buscher, Udo
    COMPUTATIONAL LOGISTICS, ICCL 2023, 2023, 14239 : 350 - 364
  • [22] Time-dependent and bi-objective vehicle routing problem with time windows
    Zhao, P. X.
    Luo, W. H.
    Han, X.
    ADVANCES IN PRODUCTION ENGINEERING & MANAGEMENT, 2019, 14 (02): : 201 - 212
  • [23] Bi-Objective Vehicle Routing for Hazardous Materials Transportation With No Vehicles Travelling in Echelon
    Wang, Nengmin
    Zhang, Meng
    Che, Ada
    Jiang, Bin
    IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS, 2018, 19 (06) : 1867 - 1879
  • [24] A tutorial on column generation and branch-and-price for vehicle routing problems
    Dominique Feillet
    4OR, 2010, 8 : 407 - 424
  • [25] A tutorial on column generation and branch-and-price for vehicle routing problems
    Feillet, Dominique
    4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2010, 8 (04): : 407 - 424
  • [26] A column generation-based heuristic for a rehabilitation patient scheduling and routing problem
    Xiao, Liyang
    Zhen, Lu
    Laporte, Gilbert
    Baldacci, Roberto
    Wang, Chenghao
    COMPUTERS & OPERATIONS RESEARCH, 2022, 148
  • [27] A column generation algorithm for the vehicle routing problem with soft time windows
    Liberatore, Federico
    Righini, Giovanni
    Salani, Matteo
    4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2011, 9 (01): : 49 - 82
  • [28] A column generation algorithm for the vehicle routing problem with soft time windows
    Federico Liberatore
    Giovanni Righini
    Matteo Salani
    4OR, 2011, 9 : 49 - 82
  • [29] A bi-objective mathematical model for hazmat vehicle routing problem with path-based risk estimation
    Xu, Tengfei
    Yang, Fengmei
    Li, Jian
    Yuan, Wenyan
    2013 SIXTH INTERNATIONAL CONFERENCE ON BUSINESS INTELLIGENCE AND FINANCIAL ENGINEERING (BIFE), 2014, : 643 - 646
  • [30] Bi-objective overlapped links vehicle routing problem for risk minimizing valuables transportation
    Mazdarani, Fatemeh
    Ghannadpour, Seyed Farid
    Zandieh, Fatemeh
    COMPUTERS & OPERATIONS RESEARCH, 2023, 153
12345