Routing a vehicle of capacity greater than one

DOI10.1016/S0166-218X(97)00074-7zbMath0895.90084OpenAlexW2000628435WikidataQ127474293 ScholiaQ127474293MaRDI QIDQ1382252

D. Massart

Publication date: 25 March 1998

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

vehicle routinggraph algorithmsmotion planningNP-completesatisfiabilitylimited capacityfeedback vertex set

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Transportation, logistics and supply chain management (90B06) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (19)

An algorithm for the one commodity pickup and delivery traveling salesman problem with restricted depot ⋮ Scheduling electric vehicles and locating charging stations on a path ⋮ Semi-preemptive routing on a linear and circular track ⋮ How to sort by walking and swapping on paths and trees ⋮ A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem ⋮ Pickup and delivery problems with autonomous vehicles on rings ⋮ How to charge while driving: scheduling point-to-point deliveries of an electric vehicle under overhead wiring ⋮ Unnamed Item ⋮ From theory to practice: maximizing revenues for on-line dial-a-ride ⋮ Improved bounds for open online dial-a-ride on the line ⋮ Tight Analysis of the Smartstart Algorithm for Online Dial-a-Ride on the Line ⋮ Energy-efficient rail guided vehicle routing for two-sided loading/unloading automated freight handling system ⋮ Euler is standing in line dial-a-ride problems with precedence-constraints ⋮ Unnamed Item ⋮ The vehicle routing problem with pickups and deliveries on some special graphs ⋮ On-line single-server dial-a-ride problems ⋮ Semi-preemptive routing on trees ⋮ The multi-commodity one-to-one pickup-and-delivery traveling salesman problem ⋮ Semi–preemptive routing on a line

Cites Work

• Nonpreemptive Ensemble Motion Planning on a Tree
• A priority queue in which initialization and queue operations takeO(loglogD) time
• Efficient Solutions to Some Transportation Problems with Applications to Minimizing Robot Arm Travel
• Preemptive Ensemble Motion Planning on a Tree
• A Note on the Complexity of a Simple Transportation Problem
• The Complexity of Near-Optimal Graph Coloring

This page was built for publication: Routing a vehicle of capacity greater than one