A tabu search algorithm for the multi-period inspector scheduling problem
From MaRDI portal
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.
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
Cites work
- scientific article; zbMATH DE number 6676558 (Why is no real title available?)
- A Heuristic for the Periodic Vehicle Routing Problem
- A Reactive Tabu Search Metaheuristic for the Vehicle Routing Problem with Time Windows
- A Tabu Search Heuristic for the Vehicle Routing Problem
- A memetic algorithm for the multiperiod vehicle routing problem with profit
- A memetic algorithm for the orienteering problem with hotel selection
- A memetic algorithm for the travelling salesperson problem with hotel selection
- A powerful route minimization heuristic for the vehicle routing problem with time windows
- A simulated annealing heuristic for the team orienteering problem with time windows
- A tabu search heuristic for periodic and multi-depot vehicle routing problems
- A two-stage heuristic with ejection pools and generalized ejection chains for the vehicle routing problem with time windows
- A two-stage tabu search algorithm with enhanced packing heuristics for the 3L-CVRP and M3L-CVRP
- A unified tabu search heuristic for vehicle routing problems with time windows
- A variable neighborhood search heuristic for periodic routing problems
- Airline crew rostering: problem types, modeling, and optimization
- Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints
- An adaptive guidance approach for the heuristic solution of a minimum multiple trip vehicle routing problem
- An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles
- An iterative three-component heuristic for the team orienteering problem with time windows
- DRIVE: Dynamic routing of independent vehicles
- Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming
- Iterated local search for the team orienteering problem with time windows
- Manpower allocation with time windows and job-teaming constraints
- Multiple pickup and delivery traveling salesman problem with last-in-first-out loading and distance constraints
- Network flows. Theory, algorithms, and applications.
- Nurse rostering problems -- a bibliographic survey.
- Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudo-polynomial model
- Staff scheduling and rostering: a review of applications, methods and models.
- The granular tabu search and its application to the vehicle-routing problem
- The orienteering problem: a survey
- The team orienteering problem with time windows: an LP-based granular variable neighborhood search
- The vehicle routing problem
- Vehicle routing problem with time windows and a limited number of vehicles.
Cited in
(9)- Hybridization of tabu search with feasible and infeasible local searches for the quadratic multiple knapsack problem
- Multiperiod multi traveling salesmen problem considering time window constraints with an application to a real world case
- 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
- Multi-period technician scheduling with experience-based service times and stochastic customers
- The curricular practical training rotation problem formulation and the assessment of rotation strategies
- A dynamic neighborhood based tabu search algorithm for real-world flight instructor scheduling problems
- Exact solution methods for the multi-period vehicle routing problem with due dates
- A PSO based algorithm with an efficient optimal split procedure for the multiperiod vehicle routing problem with profit
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)
