×

A tabu search algorithm for the multi-period inspector scheduling problem. (English) Zbl 1348.90370

Summary: This paper introduces a multi-period inspector scheduling problem (MPISP), which is a new variant of the multi-trip vehicle routing problem with time windows (VRPTW). In the MPISP, each inspector is scheduled to perform a route in a given multi-period planning horizon. At the end of each period, each inspector is not required to return to the depot but has to stay at one of the vertices for recuperation. If the remaining time of the current period is insufficient for an inspector to travel from his/her current vertex \(A\) to a certain vertex \(B\), he/she can choose either waiting at vertex \(A\) until the start of the next period or traveling to a vertex \(C\) that is closer to vertex \(B\). Therefore, the shortest transit time between any vertex pair is affected by the length of the period and the departure time. We first describe an approach of computing the shortest transit time between any pair of vertices with an arbitrary departure time. To solve the MPISP, we then propose several local search operators adapted from classical operators for the VRPTW and integrate them into a tabu search framework. In addition, we present a constrained knapsack model that is able to produce an upper bound for the problem. Finally, we evaluate the effectiveness of our algorithm with extensive experiments based on a set of test instances. Our computational results indicate that our approach generates high-quality solutions.

MSC:

90B70 Theory of organizations, manpower planning in operations research
90B06 Transportation, logistics and supply chain management
90C59 Approximation methods and heuristics in mathematical programming

Software:

Hyperheuristics; VRP
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network flowstheory, algorithms, and applications (1993), Prentice-Hall: Prentice-Hall Englewood Cliffs, N.J
[2] Azi, N.; Gendreau, M.; Potvin, J.-Y., An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles, Eur J Oper Res, 202, 3, 756-763 (2010) · Zbl 1176.90047
[3] Barnes, J. W.; Chambers, J. B., Solving the job shop scheduling problem with tabu search, IIE Trans, 27, 2, 257-263 (1995)
[4] Battarra, M.; Monaci, M.; Vigo, D., An adaptive guidance approach for the heuristic solution of a minimum multiple trip vehicle routing problem, Comput Oper Res, 36, 11, 3041-3050 (2009) · Zbl 1162.90538
[5] Bräysy, O.; Gendreau, M., Vehicle routing problem with time windows. Part Iroute construction and local search algorithms, Transp Sci, 39, 1, 104-118 (2005)
[6] Burke, E. K.; Kendall, G.; Soubeiga, E., A tabu-search hyperheuristic for timetabling and rostering, J Heuristics, 9, 6, 451-470 (2003)
[8] Castro, M.; Sörensen, K.; Vansteenwegen, P.; Goos, P., A memetic algorithm for the travelling salesperson problem with hotel selection, Comput Oper Res, 40, 7, 1716-1728 (2013) · Zbl 1348.90438
[9] Cheang, B.; Gao, X.; Lim, A.; Qin, H.; Zhu, W., Multiple pickup and delivery traveling salesman problem with last-in-first-out loading and distance constraints, Eur J Oper Res, 223, 1, 60-75 (2012) · Zbl 1253.90190
[10] Cheang, B.; Lim, A.; Rodrigues, B., Nurse rostering problems—a bibliographic survey, Eur J Oper Res, 151, 3, 447-460 (2003) · Zbl 1045.90027
[11] Chiang, W.-C.; Russell, R. A., A reactive tabu search metaheuristic for the vehicle routing problem with time windows, INFORMS J Comput, 9, 4, 417-430 (1997) · Zbl 0901.90088
[12] Cordeau, J.-F.; Gendreau, M.; Laporte, G., A tabu search heuristic for periodic and multi-depot vehicle routing problems, Networks, 30, 2, 105-119 (1997) · Zbl 0885.90037
[13] Divsalar, A.; Vansteenwegen, P.; Cattryssea, D., A variable neighborhood search method for the orienteering problem with hotel selection, Int J Product Econ, 145, 1, 150-160 (2013)
[14] Divsalar, A.; Vansteenwegen, P.; Cattryssea, D., A memetic algorithm for the orienteering problem with hotel selection, Eur J Oper Res, 237, 1, 29-49 (2014) · Zbl 1304.90220
[15] Ernst, A. T.; Jiang, H.; Krishnamoorthy, M.; Sier, D., Staff scheduling and rosteringa review of applications, methods and models, Eur J Oper Res, 153, 1, 3-27 (2004) · Zbl 1053.90034
[16] Gaudioso, M.; Paletta, G., A heuristic for the periodic vehicle routing problem, Transp Sci, 26, 2, 86-92 (1992) · Zbl 0759.90025
[17] Gendreau, M.; Hertz, A.; Laporte, G., A tabu search heuristic for the vehicle routing problem, Manag Sci, 40, 10, 1276-1290 (1994) · Zbl 0822.90053
[18] Goel, A., Vehicle scheduling and routing with drivers׳ working hours, Transp Sci, 43, 1, 17-26 (2009)
[19] Goel, A., Truck driver scheduling in the European union, Transp Sci, 44, 4, 429-441 (2010)
[21] Hemmelmayr, V. C.; Doerner, K. F.; Hartl, R. F., A variable neighborhood search heuristic for periodic routing problems, Eur J Oper Res, 195, 3, 791-802 (2009) · Zbl 1156.90307
[22] Hu, Q.; Lim, A., An iterative three-component heuristic for the team orienteering problem with time windows, Eur J Oper Res, 232, 2, 276-286 (2014) · Zbl 1305.90415
[23] Kohl, N.; Karisch, S. E., Airline crew rosteringproblem types, modeling, and optimization, Ann Oper Res, 127, 1-4, 223-257 (2004) · Zbl 1087.90031
[24] Kok, A. L.; Meyer, C. M.; Kopfer, H.; Schutten, J. M.J., A dynamic programming heuristic for the vehicle routing problem with time windows and European community social legislation, Transp Sci, 44, 4, 442-454 (2010)
[25] Labadie, N.; Mansini, R.; Melechovský, J.; Wolfler Calvo, R., The team orienteering problem with time windowsan LP-based granular variable neighborhood search, Eur J Oper Res, 220, 1, 15-27 (2012) · Zbl 1253.90048
[26] Lau, H. C.; Sim, M.; Teo, K. M., Vehicle routing problem with time windows and a limited number of vehicles, Eur J Oper Res, 148, 3, 559-569 (2003) · Zbl 1035.90014
[27] Li, Y.; Lim, A.; Rodrigues, B., Manpower allocation with time windows and job-teaming constraints, Naval Res Logist, 52, 4, 302-311 (2005) · Zbl 1140.90404
[28] Lim, A.; Zhang, X., A two-stage heuristic with ejection pools and generalized ejection chains for the vehicle routing problem with time windows, INFORMS J Comput, 19, 3, 443-457 (2007) · Zbl 1241.90051
[29] Lin, S.-W.; Yu, V. F., A simulated annealing heuristic for the team orienteering problem with time windows, Eur J Oper Res, 217, 1, 94-107 (2012) · Zbl 1244.90248
[30] Macedo, R.; Alves, C.; Valério de Carvalho, J. M.; Clautiaux, F.; Hanafi, S., Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudo-polynomial model, Eur J Oper Res, 214, 3, 536-545 (2011) · Zbl 1219.90022
[31] Montemanni, R.; Gambardella, L. M., An ant colony system for team orienteering problems with time windows, Found Comput Dec Sci, 34, 4, 287-306 (2009) · Zbl 1353.90182
[32] Nagata, Y.; Bräysy, O., A powerful route minimization heuristic for the vehicle routing problem with time windows, Oper Res Lett, 37, 5, 333-338 (2009) · Zbl 1173.90358
[33] Righini, G.; Salani, M., Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming, Comput Oper Res, 36, 4, 1191-1203 (2009) · Zbl 1162.90548
[34] Savelsbergh, M.; Sol, M., Drivedynamic routing of independent vehicles, Oper Res, 46, 4, 474-490 (1998) · Zbl 0987.90511
[35] Solomon, M. M., Algorithms for the vehicle routing and scheduling problems with time window constraints, Oper Res, 35, 2, 254-265 (1987) · Zbl 0625.90047
[36] Tang, H.; Miller-Hooks, E.; Tomastik, R., Scheduling technicians for planned maintenance of geographically distributed equipment, Transp Res Part ELogist Transp Rev, 43, 5, 591-609 (2007)
[37] Toth, P.; Vigo, D., The vehicle routing problem, vol. 9 (2002), Siam: Siam Philadelphia, PA · Zbl 0979.00026
[38] Toth, P.; Vigo, D., The granular tabu search and its application to the vehicle-routing problem, INFORMS J Comput, 15, 4, 333-346 (2003) · Zbl 1238.90141
[39] Vansteenwegen, P.; Souffriau, W.; Oudheusden, D. V., The orienteering problema survey, Eur J Oper Res, 209, 1, 1-10 (2011) · Zbl 1205.90253
[40] Vansteenwegen, P.; Souffriau, W.; Sörensen, K., The travelling salesperson problem with hotel selection, J Oper Res Soc, 63, 2, 207-217 (2012)
[41] Vansteenwegen, P.; Souffriau, W.; Vanden Berghe, G.; van Oudheusden, D., Iterated local search for the team orienteering problem with time windows, Comput Oper Res, 36, 12, 3281-3290 (2009) · Zbl 1175.90239
[42] Xu, H.; Chen, Z.-L.; Rajagopal, S.; Arunapuram, S., Solving a practical pickup and delivery problem, Transp Sci, 37, 3, 347-364 (2003)
[43] Zäpfel, G.; Bögl, M., Multi-period vehicle routing and crew scheduling with outsourcing options, Int J Prod Econ, 113, 2, 980-996 (2008)
[44] Zhang, Z.; Che, O.; Cheang, B.; Lim, A.; Qin, H., A memetic algorithm for the multiperiod vehicle routing problem with profit, Eur J Oper Res, 229, 3, 573-584 (2013) · Zbl 1317.90340
[45] Zhu, W.; Qin, H.; Lim, A.; Wang, L., A two-stage tabu search algorithm with enhanced packing heuristics for the 3L-CVRP and M3L-CVRP, Comput Oper Res, 39, 9, 2178-2195 (2012) · Zbl 1251.90346
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.