An Approximate ε-Constraint Method for the Multi-objective Undirected Capacitated Arc Routing Problem

被引:0
作者
Grandinetti, Lucio [1 ]
Guerriero, Francesca [1 ]
Lagana, Demetrio [1 ]
Pisacane, Ornella [1 ]
机构
[1] Univ Calabria, Dipartimento Elettron Informat & Sistemist, I-87030 Commenda Di Rende, Italy
来源
EXPERIMENTAL ALGORITHMS, PROCEEDINGS | 2010年 / 6049卷
关键词
Multiobjective Optimization; Capacitated Arc Routing Problem; epsilon-constraint method; ALGORITHM;
D O I
暂无
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
The Undirected Capacitated Arc Routing Problem is a classical arc routing problem arising in practical situations (road maintenance, garbage collection, mail delivery, school bus routing, etc.) with the aim of minimizing the total transportation cost of a set of routes that service a set of required edges under capacity constraints. Most of logistic companies are interested in minimizing not only the total transportation cost, they also are focused in managing the deliveries on the edges, in such a way that the duration of the longest trip does not exceed an upper time limit, to take into account the working day duration of the drivers. Moreover, all the demands of the required edges are satisfied by considering a limited number of vehicles at the depot. In this paper, the Multi-objective Undirected Capacitated Arc Routing Problem where different and competitive objectives are taken into account simultaneously, is defined and studied. Three objectives are considered in order to: minimize the total transportation cost, the longest route (makespan) and the number of vehicle used to service all the required edges (i.e., the total number of routes). To find a set of solutions belonging to the optimal pareto front, an optimization-based heuristic procedure is proposed and its performance is evaluated on a set of benchmark instances.
引用
收藏
页码:214 / 225
页数:12
相关论文
共 50 条
[41]   New lower bound for the capacitated arc routing problem [J].
Wohlk, Sanne .
COMPUTERS & OPERATIONS RESEARCH, 2006, 33 (12) :3458-3472
[42]   A multi-objective vehicle routing and scheduling problem with uncertainty in customers' request and priority [J].
Ghannadpour, S. F. ;
Noori, S. ;
Tavakkoli-Moghaddam, R. .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2014, 28 (02) :414-446
[43]   A novel multi-objective optimization model for production routing problem with sustainability dimensions [J].
Garside, Annisa Kesy ;
Bin Muhtazaruddin, Mohd Nabil ;
Ahmad, Robiah ;
Mukhlason, Ahmad .
JOURNAL OF CLEANER PRODUCTION, 2025, 502
[44]   Route Stability in the Uncertain Capacitated Arc Routing Problem [J].
Liu, Yuxin ;
Wang, Jiaxin ;
Zhao, Jingjie ;
Li, Xianghua .
FRONTIERS IN ENERGY RESEARCH, 2022, 10
[45]   Multi-objective capacitated transportation: a problem of parameters estimation, goodness of fit and optimization [J].
Gupta, Srikant ;
Ali, Irfan ;
Chaudhary, Sachin .
GRANULAR COMPUTING, 2020, 5 (01) :119-134
[46]   Multi-objective capacitated transportation: a problem of parameters estimation, goodness of fit and optimization [J].
Srikant Gupta ;
Irfan Ali ;
Sachin Chaudhary .
Granular Computing, 2020, 5 :119-134
[47]   Lower bounds for the mixed capacitated arc routing problem [J].
Gouveia, Luis ;
Mourao, Maria Candida ;
Pinto, Leonor Santiago .
COMPUTERS & OPERATIONS RESEARCH, 2010, 37 (04) :692-699
[48]   An Evolutionary Approach to the Multidepot Capacitated Arc Routing Problem [J].
Xing, Lining ;
Rohlfshagen, Philipp ;
Chen, Yingwu ;
Yao, Xin .
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2010, 14 (03) :356-374
[49]   Multi-objective optimization model for a green vehicle routing problem [J].
Jabir, E. ;
Panicker, Vinay V. ;
Sridharan, R. .
OPERATIONS MANAGEMENT IN DIGITAL ECONOMY, 2015, 189 :33-39
[50]   Solving a Multi-objective Vehicle Routing Problem with Synchronization Constraints [J].
Sarasola, Briseida ;
Doerner, Karl F. .
COMPUTATIONAL LOGISTICS (ICCL 2021), 2021, 13004 :532-546