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 条
  • [1] An c-constraint column generation-and-enumeration algorithm for Bi-Objective Vehicle Routing Problems
    Glize, Estele
    Jozefowiez, Nicolas
    Ngueveu, Sandra Ulrich
    COMPUTERS & OPERATIONS RESEARCH, 2022, 138
  • [2] Column generation based solution for bi-objective gate assignment problems
    Das, Gulesin Sena
    Gzara, Fatma
    MATHEMATICAL METHODS OF OPERATIONS RESEARCH, 2024, 100 (01) : 123 - 151
  • [3] A Column Generation-Based Gossip Algorithm for Home Healthcare Routing and Scheduling Problems
    Riazi, Sarmad
    Wigstrom, Oskar
    Bengtsson, Kristofer
    Lennartson, Bengt
    IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, 2019, 16 (01) : 127 - 137
  • [4] A column generation algorithm for vehicle scheduling and routing problems
    Ibn Faiz, Tasnim
    Vogiatzis, Chrysafis
    Noor-E-Alam, Md
    COMPUTERS & INDUSTRIAL ENGINEERING, 2019, 130 : 222 - 236
  • [5] A Column Generation Approach for Solving a Green Bi-objective Inventory Routing Problem
    Franco, Carlos
    Ramiro Lopez-Santana, Eduyn
    Mendez-Giraldo, German
    ADVANCES IN ARTIFICIAL INTELLIGENCE - IBERAMIA 2016, 2016, 10022 : 101 - 112
  • [6] A column generation-based exact solution method for seru scheduling problems
    Zhang, Zhe
    Gong, Xue
    Song, Xiaoling
    Yin, Yong
    Lev, Benjamin
    Chen, Jie
    OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 2022, 108
  • [7] Column generation algorithms for bi-objective combinatorial optimization problems with a min-max objective
    Artigues, Christian
    Jozefowiez, Nicolas
    Sarpong, Boadu M.
    EURO JOURNAL ON COMPUTATIONAL OPTIMIZATION, 2018, 6 (02) : 117 - 142
  • [8] Exact methods for mono-objective and Bi-Objective Multi-Vehicle Covering Tour Problems
    Glize, Estele
    Roberti, Roberto
    Jozefowiez, Nicolas
    Ngueveu, Sandra Ulrich
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2020, 283 (03) : 812 - 824
  • [9] A bi-objective latency based vehicle routing problem using hybrid GRASP-NSGAII algorithm
    Barma, Partha Sarathi
    Dutta, Joydeep
    Mukherjee, Anupam
    Kar, Samarjit
    INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE AND ENGINEERING MANAGEMENT, 2023, 18 (03) : 190 - 207
  • [10] A column generation-based heuristic algorithm for an inventory routing problem with perishable goods
    Tung Le
    Ali Diabat
    Jean-Philippe Richard
    Yuehwern Yih
    Optimization Letters, 2013, 7 : 1481 - 1502
12345