A tabu search algorithm for the multi-period inspector scheduling problem
From MaRDI portal
Publication:337536
DOI10.1016/J.COR.2015.01.003zbMATH Open1348.90370arXiv1409.5166OpenAlexW1996472598MaRDI QIDQ337536FDOQ337536
Authors: Hu Qin, Wei Ming, Yubin Xie, Zizhen Zhang, Andrew Lim 
Publication date: 10 November 2016
Published in: Computers \& Operations Research (Search for Journal in Brave)
Abstract: 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 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.
Full work available at URL: https://arxiv.org/abs/1409.5166
Recommendations
- Tabu search algorithm for the vehicle routing problem with time windows and multiple delivery men
- A tabu search algorithm for the multi-trip vehicle routing and scheduling problem
- A tabu search heuristic for periodic and multi-depot vehicle routing problems
- A tabu search for time-dependent multi-zone multi-trip vehicle routing problem with time windows
- Publication:4944279
Approximation methods and heuristics in mathematical programming (90C59) Transportation, logistics and supply chain management (90B06) Theory of organizations, manpower planning in operations research (90B70)
Cites Work
- Network flows. Theory, algorithms, and applications.
- A two-stage tabu search algorithm with enhanced packing heuristics for the 3L-CVRP and M3L-CVRP
- The orienteering problem: a survey
- Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming
- A memetic algorithm for the multiperiod vehicle routing problem with profit
- The vehicle routing problem
- Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints
- A unified tabu search heuristic for vehicle routing problems with time windows
- Nurse rostering problems -- a bibliographic survey.
- Staff scheduling and rostering: a review of applications, methods and models.
- Manpower allocation with time windows and job-teaming constraints
- An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles
- The team orienteering problem with time windows: an LP-based granular variable neighborhood search
- An iterative three-component heuristic for the team orienteering problem with time windows
- A variable neighborhood search heuristic for periodic routing problems
- DRIVE: Dynamic routing of independent vehicles
- A tabu search heuristic for periodic and multi-depot vehicle routing problems
- Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudo-polynomial model
- Iterated local search for the team orienteering problem with time windows
- Airline crew rostering: problem types, modeling, and optimization
- A powerful route minimization heuristic for the vehicle routing problem with time windows
- Multiple pickup and delivery traveling salesman problem with last-in-first-out loading and distance constraints
- A memetic algorithm for the orienteering problem with hotel selection
- A two-stage heuristic with ejection pools and generalized ejection chains for the vehicle routing problem with time windows
- A Tabu Search Heuristic for the Vehicle Routing Problem
- An adaptive guidance approach for the heuristic solution of a minimum multiple trip vehicle routing problem
- Vehicle routing problem with time windows and a limited number of vehicles.
- The granular tabu search and its application to the vehicle-routing problem
- Title not available (Why is that?)
- A simulated annealing heuristic for the team orienteering problem with time windows
- A memetic algorithm for the travelling salesperson problem with hotel selection
- A Heuristic for the Periodic Vehicle Routing Problem
- A Reactive Tabu Search Metaheuristic for the Vehicle Routing Problem with Time Windows
Cited In (9)
- A dynamic neighborhood based tabu search algorithm for real-world flight instructor scheduling problems
- Multiperiod multi traveling salesmen problem considering time window constraints with an application to a real world case
- Exact solution methods for the multi-period vehicle routing problem with due dates
- Multi-period technician scheduling with experience-based service times and stochastic customers
- A hybrid algorithm for time-dependent vehicle routing problem with time windows
- A heuristic algorithm for finding cost-effective solutions to real-world school bus routing problems
- Hybridization of tabu search with feasible and infeasible local searches for the quadratic multiple knapsack problem
- A PSO based algorithm with an efficient optimal split procedure for the multiperiod vehicle routing problem with profit
- The curricular practical training rotation problem formulation and the assessment of rotation strategies
Uses Software
This page was built for publication: A tabu search algorithm for the multi-period inspector scheduling problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q337536)
