A Dynamic Programming Solution of the Large-Scale Single-Vehicle Dial-A-Ride Problem with Time Windows

DOI10.1080/01966324.1986.10737198zbMath0632.90087OpenAlexW2037992565MaRDI QIDQ3770308

François Soumis, Yvan Dumas, Jacques Desrosiers

Publication date: 1986

Published in: American Journal of Mathematical and Management Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/01966324.1986.10737198

zbMATH Keywords

schedulingroutingtime window constraintsforward dynamic programmingprecedence and capacity constraintssingle-vehicle dial-a-ride problem

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39)

Related Items (43)

Asynchronous optimization of part logistics routing problem ⋮ Hybrid adaptive predictive control for a dynamic pickup and delivery problem including traffic congestion ⋮ Models and branch‐and‐cut algorithms for pickup and delivery problems with time windows ⋮ Daily aircraft routing for amphibious ready groups ⋮ An effective and fast heuristic for the dial-a-ride problem ⋮ Static pickup and delivery problems: a classification scheme and survey. (With comments and rejoinder) ⋮ A traveling salesman problem with pickups and deliveries, time windows and draft limits: case study from chemical shipping ⋮ A two-phase heuristic for an in-port ship routing problem with tank allocation ⋮ A heuristic algorithm for a dial-a-ride problem with time windows, multiple capacities, and multiple objectives ⋮ Routing problems: A bibliography ⋮ An insertion heuristic for scheduling mobility allowance shuttle transit (MAST) services ⋮ A hybrid algorithm for the multi-depot heterogeneous dial-a-ride problem ⋮ An adaptive insertion algorithm for the single-vehicle dial-a-ride problem with narrow time windows ⋮ Introducing the Localized Genetic Algorithm for Small Scale Capacitated Vehicle Routing Problems ⋮ A multi-commodity, capacitated pickup and delivery problem: the single and two-vehicle cases ⋮ Typology and literature review for dial-a-ride problems ⋮ Optimization of occupancy rate in dial-a-ride problems via linear fractional column generation ⋮ A dial-a-ride problem for client transportation in a health-care organization ⋮ Towards a decision support system for the ready concrete distribution system: a case of a Greek company. ⋮ Routing by ranking: a link analysis method for the constrained dial-a-ride problem ⋮ A lexicographic approach for the bi-objective selective pickup and delivery problem with time windows and paired demands ⋮ Mobility allowance shuttle transit (MAST) services: MIP formulation and strengthening with logic constraints ⋮ The pickup and delivery problem with time windows ⋮ Vehicle routing problems with simultaneous pick-up and delivery service. ⋮ Recent Models and Algorithms for One-to-One Pickup and Delivery Problems ⋮ A column generation approach for location-routing problems with pickup and delivery ⋮ The dial-a-ride problem: Models and algorithms ⋮ An integer \(L\)-shaped algorithm for the dial-a-ride problem with stochastic customer delays ⋮ Ship scheduling with soft time windows: An optimisation based approach ⋮ The single vehicle pickup and delivery problem with time windows: Intelligent operators for heuristic and metaheuristic algorithms ⋮ Dynamic transportation of patients in hospitals ⋮ Locating a cycle in a transportation or a telecommunications network ⋮ A tabu search heuristic for the dynamic transportation of patients between care units ⋮ A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraints ⋮ A heuristic two-phase solution approach for the multi-objective dial-a-ride problem ⋮ A new VRPPD model and a hybrid heuristic solution approach for e-tailing ⋮ A Hybrid Tabu Search and Constraint Programming Algorithm for the Dynamic Dial-a-Ride Problem ⋮ The pickup and delivery problem with transfers: formulation and a branch-and-cut solution method ⋮ A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service ⋮ Planning models for long-haul operations of postal and express shipment companies ⋮ Solving min-max shortest-path problems on a network ⋮ Perturbation heuristics for the pickup and delivery traveling salesman problem ⋮ Efficient feasibility testing for dial-a-ride problems

Cites Work

• 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
• The Traveling Salesman Problem: A Survey

This page was built for publication: A Dynamic Programming Solution of the Large-Scale Single-Vehicle Dial-A-Ride Problem with Time Windows