A large-scale neighborhood search approach to vehicle routing pick-up and delivery problem with time windows under uncertainty
Tumuluri, Praveen
Loading…
Permalink
https://hdl.handle.net/2142/88233
Description
Title
A large-scale neighborhood search approach to vehicle routing pick-up and delivery problem with time windows under uncertainty
Author(s)
Tumuluri, Praveen
Issue Date
2015-07-24
Director of Research (if dissertation) or Advisor (if thesis)
Lavanya, Marla
Department of Study
Industrial & Enterprise Systems Engineering
Discipline
Industrial Engineering
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
M.S.
Degree Level
Thesis
Keyword(s)
vehicle routing
large-scale neighbourhood search
Abstract
The vehicle routing problem with shipment pick-up and delivery with time windows (VRPPDTW) is one of the core problems that is addressed by a package delivery company in its operations. Most often, this problem has been addressed from the point of view of cost-cutting, to achieve the lowest cost possible under a given/predicted demand and service time scenario. This thesis aims to study a real-world VRPPDTW problem with side-constraints and build solutions that are cost-effective as well as robust to stochasticity in demands and service times. Even without the additional side constraints, the VRPPDTW is NP-hard. In particular, we consider the solution of VRPPDTW with side-constraints adopted by a carrier. Because of the nature as well as the size of the problem and the network, we demonstrate that the problem is combinatorially explosive. We therefore develop a large-scale neighbourhood search heuristic combined with a break-and-join heuristic and a clustering heuristic. We use this heuristic to build a set of schedules with far lower operating costs than the existing solution and effectively decrease the costs by 15% by reducing the number of routes needed to serve the shipments. We then build a framework to evaluate the performance of the solutions under stochasticity, and present results related to under stochasticity in service times.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
