×

zbMATH — the first resource for mathematics

Variable neighborhood search for the travelling deliveryman problem. (English) Zbl 1268.90068
Summary: 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.

MSC:
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
Software:
CPLEX
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 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 ) · Zbl 1269.90064
[2] 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
[3] Brimberg J, Mladenović N, Urošević D (2008) Local and variable neighborhood search for the $$k$$ -cardinality subgraph problem. J Heuristics 14:501–517 · Zbl 1211.90298 · doi:10.1007/s10732-007-9046-y
[4] Brimberg J, Mladenović N, Urošević D, Ngai E (2009) Variable neighborhood search for the heaviest $$k$$ -subgraph. Comput Oper Res 36:2885–2891 · Zbl 1162.90540 · doi:10.1016/j.cor.2008.12.020
[5] Carrizosa E, Mladenović N, Todosijević R (2011) Sum-of-square clustering on networks. Yugosl J Oper Res 21(2):157–161 · Zbl 1289.90242 · doi:10.2298/YJOR1102157C
[6] Fischetti M, Laporte G, Martello S (1993) The delivery man problem and cumulative matroids. Oper Res 41(6):1055–1064 · Zbl 0791.90062 · doi:10.1287/opre.41.6.1055
[7] Hansen P, Mldenović N, Moreno-Pérez JA (2008) Variable neighbourhood search: methods and applications. 4OR 6:319–360 · Zbl 1179.90332 · doi:10.1007/s10288-008-0089-1
[8] Hansen P, Mladenović N, Moreno Pérez JA (2010) Variable neighbourhood search: algorithms and applications. Ann Oper Res 175:367–407 · Zbl 1185.90211 · doi:10.1007/s10479-009-0657-6
[9] Ibm, ILOG CPLEX Optimizer. http://www-01.ibm.com/software/integration/optimization/cplex-optimizer
[10] 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 · Zbl 1188.90142 · doi:10.1016/j.ejor.2010.02.022
[11] 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
[12] 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 · Zbl 1265.03029 · doi:10.2298/YJOR1002229M
[13] Méndez-Díaz I, Zabala P, Lucena A (2008) A new formulation for the traveling deliveryman problem. Discret Appl Math 156:3223–3237 · Zbl 1155.90471 · doi:10.1016/j.dam.2008.05.009
[14] Mladenović N, Hansen P (1997) Variable neighborhood search. Comput Oper Res 24:1097–1100 · Zbl 0889.90119 · doi:10.1016/S0305-0548(97)00031-2
[15] 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 · Zbl 1253.90200 · doi:10.1016/j.ejor.2012.01.036
[16] 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 · Zbl 1268.90067
[17] 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 · Zbl 1221.90077 · doi:10.1007/s10288-011-0153-0
[18] Wu BY, Huang Z, Zhan F (2004) Exact algorithms for the minimum latency problem. Inf Process Lett 92(6):303–309 · Zbl 1173.68832 · doi:10.1016/j.ipl.2004.09.009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.