A large-scale neighborhood search approach to vehicle routing pick-up and delivery problem with time windows under uncertainty

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.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Industrial Engineering

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2015

Author dc:creator

• Tumuluri, Praveen

Contributors dc:contributor

• Lavanya, Marla

• vehicle routing
• large-scale neighbourhood search

Statement dc:rights

• Copyright 2015 Praveen Tumuluri

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/88233

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/88233