An optimization-based heuristic for the Multi-objective Undirected Capacitated Arc Routing Problem

作     者：Grandinetti, L. Guerriero, F. Lagana, D. Pisacane, O. 

作者机构：Univ Calabria Dipartimento Elettron Informat & Sistemist Arcavacata Di Rende CS Italy 

出 版 物：《COMPUTERS & OPERATIONS RESEARCH》 (计算机与运筹学研究)

年 卷 期：2012年第39卷第10期

页      面：2300-2309页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Multi-objective combinatorial optimization Arc routing problems Hybrid heuristic algorithm 

摘      要：The Multi-objective Undirected Capacitated Arc Routing Problem (MUCARP) is the optimization problem aimed at finding the best strategy for servicing a subset of clients localized along the links of a logistic network, by using a fleet of vehicles and optimizing more than one objective. In general, the first goal consists in minimizing the total transportation cost, and in this case the problem brings back to the well-known Undirected Capacitated Arc Routing Problem (UCARP). The motivation behind the study of the MUCARP lies in the study of real situations where companies working in the logistic distribution field deal with complex operational strategies, in which different actors (trucks, drivers, customers) have to be allocated within an unified framework by taking into account opposite needs and different employment contracts. All the previous considerations lead to the MUCARP as a benchmark optimization problem for modeling practical situations. In this paper, the MUCARP is heuristically tackled. In particular, three competitive objectives are minimized at the same time: the total transportation cost, the longest route cost (makespan) and the number of vehicles (i.e., the total number of routes). An approximation of the optimal Pareto front is determined through an optimization-based heuristic procedure. whose performances are tested and analyzed on classical benchmark instances. (C) 2011 Elsevier Ltd. All rights reserved.