A heuristic based on multi-exchange techniques for a regional fleet assignment location-routing problem

被引:38
作者
Ambrosino, Daniela [1 ]
Sciomachen, Anna [1 ]
Scutella, Maria Grazia [2 ]
机构
[1] Univ Genoa, Dipartimento Econ & Metodi Quantitat, I-16126 Genoa, Italy
[2] Univ Pisa, Dipartimento Informat, I-56127 Pisa, Italy
关键词
LARGE-SCALE;
D O I
10.1016/j.cor.2007.09.012
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
We deal with a distribution network design problem that involves location, fleet assignment and routing decisions. Specifically, the distribution network under investigation is characterized by one central depot, a set of customers split into regions, and a heterogeneous fleet of vehicles. The goal is to locate one regional depot in each region, to assign some vehicles to each region, and to design the vehicles routes, each starting and ending at the central depot, in such a way that the regional depot is visited once by all vehicles assigned to the corresponding region, the vehicle capacities are not exceeded, the customer demands are satisfied and the overall distribution cost is minimized. The study has been motivated by a real life application related to a company operating in the North of Italy. We propose a two-phase heuristic for this problem which first determines an initial feasible solution, and then improves it by using very large neighborhood search techniques. We characterize a local search neighborhood in terms of path and cyclic exchanges of customers among routes, the so-called multi-exchanges. We also extend the definition of multi-exchange in such a way to allow fleet assignment modi. cations. We then complement the multi-exchange methodology with a more classic relocation mechanism, designed to perform depot location adjustments. The proposed approach has been validated with the real life case study as well as with several randomly generated instances. The results of the extensive computational experimentation show that the proposed approach is very promising. In the case of instances characterized by a small or a medium size the heuristic was able to compute very good quality solutions in a limited amount of time. In the case of very large instances, including the real case study, the heuristic proved to be the only tool for determining feasible solutions to the problem, whereas a commercial solver such as CPLEX generally was not able to discover any feasible solution within a time limit of 25 h. (C) 2007 Elsevier Ltd. All rights reserved.
引用
收藏
页码:442 / 460
页数:19
相关论文
共 30 条
[1]   A multi-exchange heuristic for the single-source capacitated facility location problem [J].
Ahuja, RK ;
Orlin, JB ;
Pallottino, S ;
Scaparra, MP ;
Scutellà, MG .
MANAGEMENT SCIENCE, 2004, 50 (06) :749-760
[2]   A compact model and tight bounds for a combined location-routing problem [J].
Albareda-Sambola, M ;
Díaz, JA ;
Fernández, E .
COMPUTERS & OPERATIONS RESEARCH, 2005, 32 (03) :407-428
[3]   Distribution network design:: New problems and related models [J].
Ambrosino, D ;
Scutellà, MG .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2005, 165 (03) :610-624
[4]  
Ambrosino D., 2007, IMA Journal of Management Mathematics, V18, P33, DOI 10.1093/imaman/dp1012
[5]  
AMBROSINO D, 2001, THESIS U PISA ITALY
[6]  
[Anonymous], 1988, Vehicle routing: Methods and studies
[7]   Using clustering analysis location-routing in a capacitated problem [J].
Barreto, Sergio ;
Ferreira, Carlos ;
Paixao, Jose ;
Sousa Santos, Beatriz .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 179 (03) :968-977
[8]   A LOCATION BASED HEURISTIC FOR GENERAL ROUTING-PROBLEMS [J].
BRAMEL, J ;
SIMCHILEVI, D .
OPERATIONS RESEARCH, 1995, 43 (04) :649-660
[9]  
CABALLERO R, 2005, EUROPEAN J IN PRESS
[10]   Exact solution of large-scale, asymmetric traveling salesman problems [J].
Carpaneto, G ;
DellAmico, M ;
Toth, P .
ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, 1995, 21 (04) :394-409