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 条

[41] A new formulation and a column generation-based heuristic for the multiple depot vehicle scheduling problem [J].

Kulkarni, Sarang ;

Krishnamoorthy, Mohan ;

Ranade, Abhiram ;

Ernst, Andreas T. ;

Patil, Rahul .

TRANSPORTATION RESEARCH PART B-METHODOLOGICAL, 2018, 118 :457-487

[42] An exact parallel method for a bi-objective permutation flowshop problem [J].

Lemesre, J. ;

Dhaenens, C. ;

Talbi, E. G. .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 177 (03) :1641-1655

[43] Bi-objective Optimization for the Vehicle Routing Problem with Time Windows: Using Route Similarity to Enhance Performance [J].

Garcia-Najera, Abel ;

Bullinaria, John A. .

EVOLUTIONARY MULTI-CRITERION OPTIMIZATION: 5TH INTERNATIONAL CONFERENCE, EMO 2009, 2009, 5467 :275-289

[44] A column generation-based matheuristic for an inventory-routing problem with driver-route consistency [J].

Najy, Waleed ;

Archetti, Claudia ;

Diabat, Ali .

European Journal of Operational Research, 2025, 324 (02) :382-397

[45] Improving Column Generation for Vehicle Routing Problems via Random Coloring and Parallelization [J].

Yu, Miao ;

Nagarajan, Viswanath ;

Shen, Siqian .

INFORMS JOURNAL ON COMPUTING, 2022, 34 (02) :953-973

[46] An exact algorithm for IP column generation [J].

Vanderbeck, F ;

Wolsey, LA .

OPERATIONS RESEARCH LETTERS, 1996, 19 (04) :151-159

[47] Column generation-based algorithm for fragment allocation: minimizing query splitting in distributed databases [J].

Amiri, Ali .

INFORMATION TECHNOLOGY & MANAGEMENT, 2024,

[48] An Exact Algorithm for the Green Vehicle Routing Problem [J].

Andelmin, Juho ;

Bartolini, Enrico .

TRANSPORTATION SCIENCE, 2017, 51 (04) :1288-1303

[49] A new bi-objective vehicle routing-scheduling problem with cross-docking: Mathematical model and algorithms [J].

Goodarzi, Asefeh Hasani ;

Tavakkoli-Moghaddam, Reza ;

Amini, Alireza .

COMPUTERS & INDUSTRIAL ENGINEERING, 2020, 149

[50] Exact Formulation and Analysis for the Bi-Objective Insular Traveling Salesman Problem [J].

Miranda-Gonzalez, Pablo A. ;

Maturana-Ross, Javier ;

Blazquez, Carola A. ;

Cabrera-Guerrero, Guillermo .

MATHEMATICS, 2021, 9 (21)

← 1 2 3 4 5 →