NDLI: Models and efficient algorithms for pickup and delivery problems on roadmaps

Content Provider	IEEE Xplore Digital Library
Author	Treleaven, K. Pavone, M. Frazzoli, E.
Copyright Year	2012
Description	Author affiliation: Department of Aeronautics and Astronautics, Stanford University, CA 94305, USA (Pavone, M.) \|\| Laboratory for Information and Decision Systems, Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, Cambridge, 02139, USA (Treleaven, K.; Frazzoli, E.)
Abstract	One of the most common combinatorial problems in logistics and transportation—after the Traveling Salesman Problem—is the Stacker Crane Problem (SCP), where commodities or customers are associated each with a pickup location and a delivery location, and the objective is to find a minimum-length tour ‘picking up’ and ‘delivering’ all items, while ensuring the number of items on-board never exceeds a given capacity. While vastly many SCPs encountered in practice are embedded in road or road-like networks, very few studies explicitly consider such environments. In this paper, first, we formulate an environment model capturing the essential features of a “small-neighborhood” road network, along with models for omni-directional vehicles and directed vehicles. Then, we formulate a stochastic version of the unit-capacity SCP, on our road network model, where pickup/delivery sites are random points along segments of the network. Our main contribution is a polynomial-time algorithm for the problem that is asymptotically constant-factor; i.e., it produces a solution no worse than k+o(1) times the length of the optimal one, where o(1) goes to zero as the number of items grows large, almost surely. The constant k is at most 3, and for omni-directional vehicles it is provably 1, i.e., optimal. Simulations show that with a number of pickup/delivery pairs as low as 50, the proposed algorithm delivers a solution whose cost is consistently within 10% of that of an optimal solution.
Starting Page	5691
Ending Page	5698
File Size	568292
Page Count	8
File Format	PDF
ISBN	9781467320658
ISSN	07431546
e-ISBN	9781467320665
e-ISBN	9781467320641
DOI	10.1109/CDC.2012.6426164
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2012-12-10
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Vehicles Roads Cranes Mathematical model Extraterrestrial measurements Approximation methods
Content Type	Text
Resource Type	Article
Subject	Control and Optimization Control and Systems Engineering Modeling and Simulation

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

An asymptotically optimal algorithm for pickup and delivery problems

Model-based threat assessment in semi-autonomous vehicles with model parameter uncertainties

Numerical solutions to noisy systems

Threat assessment design under driver parameter uncertainty

Subspace system identification via weighted nuclear norm optimization

Design of nonlinear least-squares velocity estimation algorithms for automotive vehicles

Models and asymptotically optimal algorithms for pickup and delivery problems on roadmaps

Approximate IPA: Trading unbiasedness for simplicity

Mathematical modeling of CO2e emissions in one-to-one pickup and delivery problems

Models and efficient algorithms for pickup and delivery problems on roadmaps

Similar Documents

An asymptotically optimal algorithm for pickup and delivery problems

Model-based threat assessment in semi-autonomous vehicles with model parameter uncertainties

Numerical solutions to noisy systems

Threat assessment design under driver parameter uncertainty

Subspace system identification via weighted nuclear norm optimization

Design of nonlinear least-squares velocity estimation algorithms for automotive vehicles

Models and asymptotically optimal algorithms for pickup and delivery problems on roadmaps

Approximate IPA: Trading unbiasedness for simplicity

Mathematical modeling of CO2e emissions in one-to-one pickup and delivery problems

Models and efficient algorithms for pickup and delivery problems on roadmaps