Modeling and solving a vehicle-sharing problem considering multiple alternative modes of transport

• URL: http://arxiv.org/abs/2003.08207v2
• Date: Wed, 28 Sep 2022 12:20:54 GMT
• Title: Modeling and solving a vehicle-sharing problem considering multiple alternative modes of transport
• Authors: Miriam Enzi, Sophie N. Parragh, David Pisinger
• Abstract summary: We consider vehicle-sharing in a company having one or more depots and a fixed number of users, i.e. employees. A vehicle must be used for a full trip of a user from depot to depot. We aim at assigning vehicles to user trips so as to maximize savings compared to other modes of transport.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Motivated by the change in mobility patterns, we present a scheduling approach for a vehicle-sharing problem, considering several alternative modes of transport, from a company viewpoint with centralized planning. We consider vehicle-sharing in a company having one or more depots and a fixed number of users, i.e. employees. The users have appointments with a fixed location and fixed start and end times. A vehicle must be used for a full trip of a user from depot to depot. We aim at assigning vehicles to user trips so as to maximize savings compared to other modes of transport. We first consider that only one type of vehicle is used, and second that multiple vehicle types can be used. For the first case, we show that the vehicle-sharing problem can be formulated as a minimum-cost flow problem. Secondly, if multiple types of vehicles are available the problem can be formulated as a multi-commodity flow problem. These formulations make the problem applicable in daily operations due to efficient solution methods. We provide a comprehensive computational study for both cases on instances based on demographic, spatial, and economic data of Vienna. We show that our formulations for this problem solve these instances in a few seconds, which makes them usable in an online booking system. In the analysis we discuss different potential settings. We study the optimal composition of a shared fleet, restricted sets of modes of transport, and variations of the objective function.

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)
• Coalitional Bargaining via Reinforcement Learning: An Application to Collaborative Vehicle Routing [49.00137468773683]
  Collaborative Vehicle Routing is where delivery companies cooperate by sharing their delivery information and performing delivery requests on behalf of each other. This achieves economies of scale and thus reduces cost, greenhouse gas emissions, and road congestion. But which company should partner with whom, and how much should each company be compensated? Traditional game theoretic solution concepts, such as the Shapley value or nucleolus, are difficult to calculate for the real-world problem of Collaborative Vehicle Routing.
  arXiv  Detail & Related papers  (2023-10-26T15:04:23Z)
• Multi-Agent Neural Rewriter for Vehicle Routing with Limited Disclosure of Costs [65.23158435596518]
  Solving the multi-vehicle routing problem as a team Markov game with partially observable costs. Our multi-agent reinforcement learning approach, the so-called multi-agent Neural Rewriter, builds on the single-agent Neural Rewriter to solve the problem by iteratively rewriting solutions.
  arXiv  Detail & Related papers  (2022-06-13T09:17:40Z)
• 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)
• Optimizing Planning Service Territories by Dividing Into Compact Several Sub-areas Using Binary K-means Clustering According Vehicle Constraints [0.0]
  VRP (Vehicle Routing Problem) is an NP hard problem, and it has attracted a lot of research interest. In this paper we propose new algorithms for producing such clusters/groups that do not exceed vehicles maximum capacity.
  arXiv  Detail & Related papers  (2020-10-21T12:19:08Z)
• The bi-objective multimodal car-sharing problem [0.0]
  The aim of the BiO-MMCP is to determine the optimal mode of transport assignment for trips. As user satisfaction is a crucial aspect in shared mobility systems, we consider user preferences in a second objective. We develop a branch-and-cut algorithm which is embedded in two bi-objective frameworks.
  arXiv  Detail & Related papers  (2020-10-18T13:48:17Z)
• Multi-Agent Routing Value Iteration Network [88.38796921838203]
  We propose a graph neural network based model that is able to perform multi-agent routing based on learned value in a sparsely connected graph. We show that our model trained with only two agents on graphs with a maximum of 25 nodes can easily generalize to situations with more agents and/or nodes.
  arXiv  Detail & Related papers  (2020-07-09T22:16:45Z)
• Equitable and Optimal Transport with Multiple Agents [48.17429789586127]
  We introduce an extension of the Optimal Transport problem when multiple costs are involved. We aim to share equally between agents the work of transporting one distribution to another. Another point of view is when the goal is to partition equitably goods between agents according to their heterogeneous preferences.
  arXiv  Detail & Related papers  (2020-06-12T15:15:41Z)
• 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.