Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/35096
Title: On-time delivery probabilistic models for stochastic vehicle routing problems
Authors: Zhang, Junlong
Advisors: Lam, William H. K. (CEE)
Sumalee, Agachai (CEE)
Keywords: Transportation problems (Programming)
Delivery of goods.
Issue Date: 2015
Publisher: The Hong Kong Polytechnic University
Abstract: Attention is increasing on on-time delivery in the distribution and logistics industry. On-time delivery directly influences customer service levels and is a key delivery service performance measure. Owing to uncertainties in customer demands and travel time variations in urban road networks, on-time deliveries to customers cannot be guaranteed. Travel times in urban road networks are highly stochastic due to roadway capacity variations and traffic demand fluctuations. Customer demands are also varied when a vehicle is on the way to deliver goods to various customer locations. The vehicle capacity may thus be exceeded along a planned delivery route. The vehicle may have to return to the depot to reload. This would lead to additional travel times or delays for delivery. The vehicle routing problem (VRP) involves planning a set of minimum-cost delivery routes for the vehicles of a distribution company to serve a group of geographically scattered customers. It has broad applications in distribution and logistics management fields and has been extensively studied over the past decades. One important variant of the VRP is called the VRP with time windows. In this problem, each customer may require to be served within a given time interval (i.e. time window). Due to uncertainties in customer demands and travel time variations in urban road networks as stated above, on-time deliveries to these customers cannot be ensured. This is a critical issue in practical scenarios. However, little attention has been paid to specifically address the on-time delivery issue under uncertainties in travel times and/or customer demands. In view of the above, this thesis investigates the on-time delivery issue in two stochastic VRPs: the VRP with stochastic travel times and time windows (VRPSTT-TW) and the VRP with stochastic demands and time windows (VRPSD-TW). The thesis contributes to the literature of stochastic VRPs in the following aspects.
Firstly, a new stochastic programming model is proposed for the VRPSTT-TW (and is later extended for the VRPSD-TW) that explicitly addresses the on-time delivery issue under uncertainties in travel times. This model is formulated from the point view of an operator who wishes to reduce the total expected cost of delivery (and particularly to reduce the cost of deploying the required vehicles), but at the same time would like to achieve certain service level requirements in terms of on-time deliveries to customers. More specifically, the proposed model embeds probabilistic customer service level constraints within a traditional stochastic programming with recourse model. The proposed model can be used to design a set of delivery routes that minimizes the total expected cost of delivery (including the cost of deploying the required vehicles), while ensuring a given on-time delivery probability to each customer. Secondly, an iterated tabu search heuristic algorithm is developed to solve the proposed model for the VRPSTT-TW. To minimize the number of vehicles required, a route reduction mechanism is designed and incorporated in the developed heuristic algorithm. A discrete approximation method is also presented for estimating the distribution of the vehicle arrival time at each customer location in the presence of time windows. Using this approximation method, solutions to the proposed model can be evaluated without suffering restrictions on the assumption of travel time distributions. Thirdly, a new probabilistic model is proposed for the VRPSD-TW that addresses the on-time delivery issue under uncertainties in customer demands from the customer perspective. This model seeks to plan a set of delivery routes that maximizes the sum of on-time delivery probabilities to all the customers, provided that the maximum number of vehicles for delivery of goods is given and fixed. The proposed model attempts to answer the question of "what is the best possible on-time delivery performance of a distribution company with a fixed-size fleet of vehicles for delivery of goods?" Fourthly, the applicability of a preventive restocking (PR) policy is examined for the models proposed for the VRPSD-TW. Under a traditional detour-to-depot (DTD) recourse policy, a vehicle would return to the depot to reload only when the remaining vehicle capacity becomes zero or is exceeded along a planned delivery route. Under the PR policy, the vehicle would return to the depot to reload if the remaining vehicle capacity is below a predetermined level. In this thesis, it is shown that the PR policy can help to generate delivery solutions better than those resulting from the traditional DTD recourse policy.
Description: PolyU Library Call No.: [THS] LG51 .H577M CEE 2015 Zhang
xx, 119 leaves :illustrations ;30 cm
URI: http://hdl.handle.net/10397/35096
Rights: All rights reserved.
Appears in Collections:Thesis

Files in This Item:
File Description SizeFormat 
b28068695_link.htmFor PolyU Users203 BHTMLView/Open
b28068695_ir.pdfFor All Users (Non-printable)6.35 MBAdobe PDFView/Open
Show full item record

Page view(s)

103
Last Week
4
Last month
Checked on Mar 26, 2017

Download(s)

60
Checked on Mar 26, 2017

Google ScholarTM

Check



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.