Variable neighborhood search based algorithms to solve a rich k-travelling repairmen problem
- PDF / 550,489 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 98 Downloads / 180 Views
Variable neighborhood search based algorithms to solve a rich k-travelling repairmen problem Sana Frifita1
· Ines Mathlouthi2 · Malek Masmoudi3 · Abdelaziz Dammak1
Received: 22 June 2018 / Accepted: 10 February 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract In this paper, we consider a Rich k-travelling repairmen problem (R-k-TRP), motivated by an application for the maintenance and repair of electronic transaction equipment. It consists of designing routes of polyvalent repairmen to perform customers requests. The objective is to minimize a linear combination of total weighted travelled distance, breaks and overtime, minus gain associated with performed requests, under a set of constraints such as multiple time windows, parts inventory, breaks, and special parts. A benchmark of small and medium instances are considered from literature and new larger instances are generated. A Variable Neighborhood Search (VNS) and a General Variable Neighborhood Search algorithms (GVNS), both coupled with a technique called Adaptive memory (AM), are proposed to address this problem. The computational results show the effectiveness and efficiency of the GVNS with AM for solving the R-k-TRP, in comparison with other provided VNS algorithms and the current state of the art Branch and Price method. Keywords R-k-TRP · multiple time windows · inventory · GVNS · Adaptive memory
B
Sana Frifita [email protected] Ines Mathlouthi [email protected] Malek Masmoudi [email protected] Abdelaziz Dammak [email protected]
1
Laboratory of Modeling and Optimization for Decisional, Industrial and Logistic Systems, Faculty of Economics and Management of Sfax, University of Sfax, 3018 Sfax, Tunisia
2
Department of Computer Science and Operations Research, University of Montreal, Quebec, Canada
3
Faculty of Sciences and Techniques, University of Lyon, University of Jean Monnet Saint Etienne, 42000 Saint-Etienne, France
123
S. Frifita et al.
1 Introduction The k-traveling repairman problem (k-TRP), which is a special case of the TRP, consists of routing repairmen to serve requests taking into account different constraints. The TRP belongs to the Vehicle Routing Problems [8] and is related in particular to the VRP with Time windows [12]. There are, however, significant differences such as large service times and parts inventory. Despite their numerous practical applications, the TRP has received limited attention in the literature compared to the VRP. Dimitris and Garrett [3] have proposed a generic mathematical model for a Dynamic TRP where the objective is to minimize the waiting time in a stochastic and dynamically changing environment. They have derived lower bounds on the optimal system time and proposed several policies for the Dynamic TRP, in order to analyze their behavior. García et al. [9] have provided a linear algorithm for the TRP with time windows. The same problem has been solved later by Frederickson and Wittman [4] with an approximation algorithm. Salehipour
Data Loading...
