Variable neighborhood search for the travelling deliveryman problem
Tóm tắt
A travelling deliveryman needs to find a tour such that the total waiting time of all the customers he has to visit is minimum. The deliveryman starts his tour at a depot, travelling at constant velocity. In this paper we suggest a general variable neighborhood search based heuristic to solve this NP-hard combinatorial optimization problem. We combine several classical neighborhood structures and design data structure to store and update the incumbent solution efficiently. In this way, we are able to explore neighborhoods as efficiently as when solving the travelling salesman problem. Computational results obtained on usual test instances show that our approach outperforms recent heuristics from the literature.
Tài liệu tham khảo
Abeledo H, Fukasawa R, Pessoa A, Uchoa E (2010) The time dependent traveling salesman problem: polyhedra and algorithm. Optim Online (http://www.optimization-online.org/DB_HTML/2010/12/2872.html)
Blum A, Chalasani P, Coppersmish D, Pulleyblank B, Raguavan P, Sudan M (1994) The minumum latency problem. In: Proceedings of 26th annual ACM symposium on theory of computting, Montreal
Brimberg J, Mladenović N, Urošević D (2008) Local and variable neighborhood search for the \(k\)-cardinality subgraph problem. J Heuristics 14:501–517
Brimberg J, Mladenović N, Urošević D, Ngai E (2009) Variable neighborhood search for the heaviest \(k\)-subgraph. Comput Oper Res 36:2885–2891
Carrizosa E, Mladenović N, Todosijević R (2011) Sum-of-square clustering on networks. Yugosl J Oper Res 21(2):157–161
Fischetti M, Laporte G, Martello S (1993) The delivery man problem and cumulative matroids. Oper Res 41(6):1055–1064
Hansen P, Mldenović N, Moreno-Pérez JA (2008) Variable neighbourhood search: methods and applications. 4OR 6:319–360
Hansen P, Mladenović N, Moreno Pérez JA (2010) Variable neighbourhood search: algorithms and applications. Ann Oper Res 175:367–407
Ibm, ILOG CPLEX Optimizer. http://www-01.ibm.com/software/integration/optimization/cplex-optimizer
Ilić A, Urošević D, Brimberg J, Mladenović N (2010) Variable neighborhood search for solving the uncapacitated single allocation \(p\)-hub median problem. Eur J Oper Res 206:289–300
Johnson DS, McGeoch LA (1996) The travelling salesman problem: a case study in local optimization. In: Aarts EHL, Lenstra JK (eds) Local search in combinatorial optimization. Wiley, New York
Markoski B, Hotomski P, Malbaški D, Obradović D (2011) Dijkstra’s interpretation of the approach to solving a problem of program correctness. Yugosl J Oper Res 20:229–236
Méndez-Díaz I, Zabala P, Lucena A (2008) A new formulation for the traveling deliveryman problem. Discret Appl Math 156:3223–3237
Mladenović N, Hansen P (1997) Variable neighborhood search. Comput Oper Res 24:1097–1100
Mladenović N, Urošević D, Hanafi S, Ilić A (2012) A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem. Eur J Oper Res 220:270–285
Mladenović N, Urošević D, Todosijević R. An efficient GVNS for solving traveling salesman problem with time windows. Yugosl J Oper Res. doi:10.2298/YJOR120530015M
Salehipour A, Sörensen K, Goos P, Brysy O (2011) Efficient GRASP+VND and GRASP+VNS metaheuristics for the traveling repairman problem. 4OR-Q J Oper Res 9(2):189–209
Wu BY, Huang Z, Zhan F (2004) Exact algorithms for the minimum latency problem. Inf Process Lett 92(6):303–309