Modeling and solving the multimodal car- and ride-sharing problem
- URL: http://arxiv.org/abs/2001.05490v2
- Date: Wed, 28 Sep 2022 12:58:19 GMT
- Title: Modeling and solving the multimodal car- and ride-sharing problem
- Authors: Miriam Enzi, Sophie N. Parragh, David Pisinger and Matthias
Prandtstetter
- Abstract summary: 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.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We introduce the multimodal car- and ride-sharing problem (MMCRP), in which a
pool of cars is used to cover a set of ride requests while uncovered requests
are assigned to other modes of transport (MOT). A car's route consists of one
or more trips. Each trip must have a specific but non-predetermined driver,
start in a depot and finish in a (possibly different) depot. Ride-sharing
between users is allowed, even when two rides do not have the same origin
and/or destination. A user has always the option of using other modes of
transport according to an individual list of preferences.
The problem can be formulated as a vehicle scheduling problem. In order to
solve the problem, an auxiliary graph is constructed in which each trip
starting and ending in a depot, and covering possible ride-shares, is modeled
as an arc in a time-space graph. We propose a two-layer decomposition algorithm
based on column generation, where the master problem ensures that each request
can only be covered at most once, and the pricing problem generates new
promising routes by solving a kind of shortest-path problem in a time-space
network. Computational experiments based on realistic instances are reported.
The benchmark instances are based on demographic, spatial, and economic data of
Vienna, Austria. We solve large instances with the column generation based
approach to near optimality in reasonable time, and we further investigate
various exact and heuristic pricing schemes.
Related papers
- Contextual Stochastic Vehicle Routing with Time Windows [47.91283991228738]
We study the vehicle routing problem with time windows (VRPTW) and travel times.
We introduce the contextual VRPTW, which minimizes the total transportation cost and expected late arrival penalties conditioned on the observed features.
We present novel data-driven prescriptive models that use historical data to provide an approximate solution to the problem.
arXiv Detail & Related papers (2024-02-10T14:56:36Z) - 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) - MultiZenoTravel: a Tunable Benchmark for Multi-Objective Planning with
Known Pareto Front [71.19090689055054]
Multi-objective AI planning suffers from a lack of benchmarks exhibiting known Pareto Fronts.
We propose a tunable benchmark generator, together with a dedicated solver that provably computes the true Pareto front of the resulting instances.
We show how to characterize the optimal plans for a constrained version of the problem, and then show how to reduce the general problem to the constrained one.
arXiv Detail & Related papers (2023-04-28T07:09:23Z) - Multi-Start Team Orienteering Problem for UAS Mission Re-Planning with
Data-Efficient Deep Reinforcement Learning [9.877261093287304]
We study a mission re-planning problem where vehicles are initially located away from the depot and have different amounts of fuel.
We develop a policy network with self-attention on each partial tour and encoder-decoder attention between the partial tour and the remaining nodes.
We propose a modified REINFORCE algorithm where the greedy rollout baseline is replaced by a local mini-batch baseline based on multiple, possibly non-duplicate sample rollouts.
arXiv Detail & Related papers (2023-03-02T15:15:56Z) - Machine-learning-based arc selection for constrained shortest path
problems in column generation [5.08128537391027]
In this work, we propose a new pricing algorithm based on machine learning.
The objective is to reduce the size of the network and accelerate the PP, keeping only the arcs that have a high chance to be part of the linear relaxation solution.
The method has been applied to two specific problems: the vehicle and crew scheduling problem in public transit and the vehicle routing problem with time windows.
arXiv Detail & Related papers (2022-01-07T16:49:12Z) - A Case Study of Vehicle Route Optimization [2.2101681534594237]
In this work, we incorporate the main relevant real-world constraints and requirements.
We propose a two-stage strategy and a Timeline algorithm for time windows and pause times.
Our evaluation of eight different problem instances against four state-of-the-art algorithms shows that our approach handles all given constraints in a reasonable time.
arXiv Detail & Related papers (2021-11-17T13:10:55Z) - 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) - Modeling and solving a vehicle-sharing problem considering multiple
alternative modes of transport [0.0]
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.
arXiv Detail & Related papers (2020-03-17T11:12:20Z) - 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)
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.