A metaheuristic for crew scheduling in a pickup-and-delivery problem with time windows

• URL: http://arxiv.org/abs/2102.01780v1
• Date: Tue, 2 Feb 2021 22:14:10 GMT
• Title: A metaheuristic for crew scheduling in a pickup-and-delivery problem with time windows
• Authors: Mauro Lucci, Daniel Sever\'in, Paula Zabala
• Abstract summary: A vehicle routing and crew scheduling problem (VRCSP) consists of simultaneously planning the routes of a fleet of vehicles and scheduling the crews. We present a VRCSP where pickup-and-delivery requests with time windows have to be fulfilled over a given planning horizon by using trucks and drivers. We find high-quality solutions on instances of 100 requests spread across 15 cities with a fleet of 12-32 trucks in less than an hour.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A vehicle routing and crew scheduling problem (VRCSP) consists of simultaneously planning the routes of a fleet of vehicles and scheduling the crews, where the vehicle-crew correspondence is not fixed through time. This allows a greater planning flexibility and a more efficient use of the fleet, but in counterpart, a high synchronisation is demanded. In this work, we present a VRCSP where pickup-and-delivery requests with time windows have to be fulfilled over a given planning horizon by using trucks and drivers. Crews can be composed of 1 or 2 drivers and any of them can be relieved in a given set of locations. Moreover, they are allowed to travel among locations with non-company shuttles, at an additional cost that is minimised. As our problem considers distinct routes for trucks and drivers, we have an additional flexibility not contemplated in other previous VRCSP given in the literature where a crew is handled as an indivisible unit. We tackle this problem with a two-stage sequential approach: a set of truck routes is computed in the first stage and a set of driver routes consistent with the truck routes is obtained in the second one. We design and evaluate the performance of a metaheuristic based algorithm for the latter stage. Our algorithm is mainly a GRASP with a perturbation procedure that allows reusing solutions already found in case the search for new solutions becomes difficult. This procedure together with other to repair infeasible solutions allow us to find high-quality solutions on instances of 100 requests spread across 15 cities with a fleet of 12-32 trucks (depending on the planning horizon) in less than an hour. We also conclude that the possibility of carrying an additional driver leads to a decrease of the cost of external shuttles by about 60% on average with respect to individual crews and, in some cases, to remove this cost completely.

Related papers

• An Online Approach to Solving Public Transit Stationing and Dispatch Problem [7.948662269574215]
  Transit agencies keep a limited number of vehicles in reserve and dispatch them to relieve the affected routes during disruptions. This paper describes a principled approach using non-myopic sequential decision procedures to solve the problem. Our experiments show that the proposed framework serves 2% more passengers while reducing deadhead miles by 40%.
  arXiv  Detail & Related papers  (2024-03-05T21:48:29Z)
• Solving the Team Orienteering Problem with Transformers [46.93254771681026]
  Route planning for a fleet of vehicles is an important task in applications such as package delivery, surveillance, or transportation. This paper presents a multi-agent route planning system capable of solving the Team Orienteering Problem in a very fast and accurate manner.
  arXiv  Detail & Related papers  (2023-11-30T16:10:35Z)
• Fair collaborative vehicle routing: A deep multi-agent reinforcement learning approach [49.00137468773683]
  Collaborative vehicle routing occurs when carriers collaborate through sharing their transportation requests and performing transportation requests on behalf of each other. Traditional game theoretic solution concepts are expensive to calculate as the characteristic function scales exponentially with the number of agents. We propose to model this problem as a coalitional bargaining game solved using deep multi-agent reinforcement learning.
  arXiv  Detail & Related papers  (2023-10-26T15:42:29Z)
• DC-MRTA: Decentralized Multi-Robot Task Allocation and Navigation in Complex Environments [55.204450019073036]
  We present a novel reinforcement learning based task allocation and decentralized navigation algorithm for mobile robots in warehouse environments. We consider the problem of joint decentralized task allocation and navigation and present a two level approach to solve it. We observe improvement up to 14% in terms of task completion time and up-to 40% improvement in terms of computing collision-free trajectories for the robots.
  arXiv  Detail & Related papers  (2022-09-07T00:35:27Z)
• Supervised Permutation Invariant Networks for Solving the CVRP with Bounded Fleet Size [3.5235974685889397]
  Learning to solve optimization problems, such as the vehicle routing problem, offers great computational advantages. We propose a powerful supervised deep learning framework that constructs a complete tour plan from scratch while respecting an apriori fixed number of vehicles. In combination with an efficient post-processing scheme, our supervised approach is not only much faster and easier to train but also competitive results.
  arXiv  Detail & Related papers  (2022-01-05T10:32:18Z)
• Integrated Vehicle Routing and Monte Carlo Scheduling Approach for the Home Service Assignment, Routing, and Scheduling Problem [0.2578242050187029]
  We formulate and solve the H-SARA Problem motivated by home services management. We assume that travel times, durations, and customer cancellations are service management. We introduce two different models of cancellation and their associated impacts on routing and scheduling. We present insights into the problem and a series of numerical experiments that illustrate properties of the optimal routing, scheduling, and the impact of the Route Fracture Metaheuristic for both models of cancellation.
  arXiv  Detail & Related papers  (2021-06-30T16:12:14Z)
• An SMT Based Compositional Model to Solve a Conflict-Free Electric Vehicle Routing Problem [2.64699517152535]
  The Electric Conflict-Free Vehicle Routing Problem (CF-EVRP) involves constraints such as limited operating range of the vehicles, time windows on the delivery to the customers, and limited capacity on the number of vehicles the road segments can accommodate. We develop a compositional model that breaks down the problem into smaller and simpler sub-problems and provides sub-optimal, feasible solutions.
  arXiv  Detail & Related papers  (2021-06-10T20:37:46Z)
• Flatland Competition 2020: MAPF and MARL for Efficient Train Coordination on a Grid World [49.80905654161763]
  The Flatland competition aimed at finding novel approaches to solve the vehicle re-scheduling problem (VRSP) The VRSP is concerned with scheduling trips in traffic networks and the re-scheduling of vehicles when disruptions occur. The ever-growing complexity of modern railway networks makes dynamic real-time scheduling of traffic virtually impossible.
  arXiv  Detail & Related papers  (2021-03-30T17:13:29Z)
• A Maximum Independent Set Method for Scheduling Earth Observing Satellite Constellations [41.013477422930755]
  This paper introduces a new approach for solving the satellite scheduling problem by generating an infeasibility-based graph representation of the problem. It is tested on a scenarios of up to 10,000 requested imaging locations for the Skysat constellation of optical satellites as well as simulated constellations of up to 24 satellites.
  arXiv  Detail & Related papers  (2020-08-15T19:32:21Z)
• Reinforcement Learning Based Vehicle-cell Association Algorithm for Highly Mobile Millimeter Wave Communication [53.47785498477648]
  This paper investigates the problem of vehicle-cell association in millimeter wave (mmWave) communication networks. We first formulate the user state (VU) problem as a discrete non-vehicle association optimization problem. The proposed solution achieves up to 15% gains in terms sum of user complexity and 20% reduction in VUE compared to several baseline designs.
  arXiv  Detail & Related papers  (2020-01-22T08:51:05Z)
• Modeling and solving the multimodal car- and ride-sharing problem [0.0]
  We introduce the multimodal car- and ride-sharing problem (MMCRP) A pool of cars is used to cover a set of ride requests while uncovered requests are assigned to other modes of transport. We propose a two-layer decomposition algorithm based on column generation.
  arXiv  Detail & Related papers  (2020-01-15T09:43:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.