Vehicle routing problems with alternative paths: an application to on-demand transportation

DOI10.1016/j.ejor.2009.10.002zbMath1178.90037OpenAlexW2059317120MaRDI QIDQ2654320

Dominique Feillet, Didier Josselin, Thierry Garaix, Christian Artigues

Publication date: 15 January 2010

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2009.10.002

zbMATH Keywords

multigraphdynamic programmingvehicle routingdial-a-ride problemshortest path problem with resource constraintson-demand transportation

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Transportation, logistics and supply chain management (90B06) Dynamic programming (90C39)

Related Items

The time-dependent shortest path and vehicle routing problem, Coordinated routing of electric commercial vehicles with intra-route recharging and en-route battery swapping, Event-based MILP models for ridepooling applications, The hybrid electric vehicle-traveling salesman problem, Pricing routines for vehicle routing with time windows on road networks, Empirical analysis for the VRPTW with a multigraph representation for the road network, Vehicle routing on road networks: how good is Euclidean approximation?, A sample average approximation approach for the stochastic dial-a-ride problem on a multigraph with user satisfaction, A concise guide to existing and emerging vehicle routing problem variants, The vehicle routing problem with arrival time diversification on a multigraph, An adaptive insertion algorithm for the single-vehicle dial-a-ride problem with narrow time windows, A branch-and-price algorithm for a routing problem with inbound and outbound requests, Safe and secure vehicle routing: a survey on minimization of risk exposure, Secure and efficient routing on nodes, edges, and arcs of simple‐graphs and of multi‐graphs, The Steiner bi-objective shortest path problem, Estimating energy consumption and charging duration of electric vehicle in multigraph, Typology and literature review for dial-a-ride problems, Optimization of occupancy rate in dial-a-ride problems via linear fractional column generation, A distance function for computing on finite subsets of Euclidean spaces, Multigraph modeling and adaptive large neighborhood search for the vehicle routing problem with time windows, Facing robustness as a multi-objective problem: a bi-objective shortest path problem in smart regions, The time-dependent vehicle routing problem with time windows and road-network information, Optimizing large on-demand transportation systems through stochastic conic programming, Routing a mix of conventional, plug-in hybrid, and electric vehicles, Tabu search for the time-dependent vehicle routing problem with time windows on a road network, A risk-constrained time-dependent cash-in-transit routing problem in multigraph under uncertainty, A comparison of genetic representations for multi-objective shortest path problems on multigraphs

Uses Software

• VRP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The pickup and delivery problem with time windows
• The dial-a-ride problem (DARP): variants, modeling issues and algorithms
• The traveling salesman problem and its variations
• A survey and annotated bibliography of multiobjective combinatorial optimization
• A heuristic algorithm for a dial-a-ride problem with time windows, multiple capacities, and multiple objectives
• A label correcting approach for solving bicriterion shortest-path problems
• A dial-a-ride problem for client transportation in a health-care organization
• A two-phase insertion technique of unexpected customers for a dynamic dial-a-ride problem
• Object modeling and path computation for multimodal travel systems
• The dial-a-ride problem: Models and algorithms
• The multiple disposal facilities and multiple inventory locations rollon-rolloff vehicle routing problem
• Solving the multidimensional multiple-choice knapsack problem by constructing convex hulls
• A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraints
• A reactive local search-based algorithm for the multiple-choice multi-dimensional knapsack problem
• A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows
• Drive: Dynamic Routing of Independent Vehicles
• Solving the Convex Cost Integer Dual Network Flow Problem
• A Branch-and-Cut Algorithm for the Dial-a-Ride Problem
• Solving the Dial-a-Ride problem using genetic algorithms
• Optimizing Single Vehicle Many-to-Many Operations with Desired Delivery Times: I. Scheduling
• Optimizing Single Vehicle Many-to-Many Operations with Desired Delivery Times: II. Routing
• Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
• A Generalized Permanent Labelling Algorithm For The Shortest Path Problem With Time Windows
• An algorithm for the resource constrained shortest path problem
• Heuristic Algorithms for the Handicapped Persons Transportation Problem
• An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems
• Models and branch‐and‐cut algorithms for pickup and delivery problems with time windows
• Column Generation
• Shortest Path Problems with Resource Constraints
• Heuristics from Nature for Hard Combinatorial Optimization Problems
• Label correcting methods to solve multicriteria shortest path problems