CUHK electronic theses & dissertations collection

In this dissertation, we aim to investigate some delivery planning problems under different aspects of uncertain conditions in order to present some insights on how to develop more efficient and effective logistics solutions in the challenging, dynamic and competitive industry of express delivery nowadays.Lastly, we introduce a travel time estimation method which can be considered as an upstream extension on the first delivery planning problem or any routing problems that require travel time in a road network as an input parameter. We realize that different trips may traverse on some links that are transited by other trips as well; and therefore linear and quadratic programming models can be developed to infer the travel time of any road segments which are traversed by more than one trip from the consideration of the common road segments of various trips. Bus routes information is proposed as the data source because of their coverage on the road network and their data available. Robustness of the proposed models is evaluated according to the deviation between the resultant inferences and the means of the segment travel times. It is found that the basic models suffer from a fundamental problem of underspecification issue if the number of observed trips (i.e. constraints) is fewer than the number of road segments (i.e. variables) to be estimated. Therefore, two additional types of constraints are introduced to address these issues.The focus of the second delivery planning problem addressed in this dissertation is switched to the randomness of the demands at the delivery locations. We consider a single-depot problem in which a large volume of packages have to be delivered in a dense and small area with a lot of high-rise buildings within an extremely tight delivery commitment time window. At each vertex, the package volume (i.e. demand) is a highly stochastic variable and its service time is also dependent on the demand. This version of problem is typically faced by express service providers which offer premium express services to customers that are protected by the money back guarantee (MBG) condition. We name this version of problem as a time-constrained vehicle routing problem with stochastic demands and service times (SVRP-D). Since both the demand and service time of a vertex are stochastic, the vehicle capacity and the commitment-time (i.e. deadline) constraints may not be satisfied after the demands are realized, and recourse action is thus necessary to "rescue" the "infeasible" delivery plan through additional effort and cost. Three typical recourse actions are independently considered: (1) restocking; (2) outsourcing; and (3) reassignment. A two-stage stochastic integer programming is proposed such that the first-stage problem is to determine a set of a priori routes which minimize the vehicle travel cost and the cost for any known recourse actions. Dependent on a first-stage solution, the second-stage problem is to decide the optimal recourse plan with least cost according to the pre-determined recourse action.Two delivery planning problems and one travel time estimation model under various aspects of randomness are addressed in this dissertation. The first delivery planning problem considers an extension on a well-known problem---the vehicle routing problem with time windows (VRPTW), where the travel time required between each delivery location is a stochastic variable, instead of a fixed value. We name this version of the VRPTW as a vehicle routing problem with time windows and stochastic travel times (VRPTWST). A two-stage stochastic integer programming with recourse model is developed and its objective is to minimize the vehicle travel cost together with the expected loss due to the violation of the delivery time windows. An exact branch-and-cut (B&C) algorithm is proposed. This algorithm is effective for small-size problems, e.g. instances with only 8 vertices. For larger-size problems, some modifications on the B&C algorithm are suggested to improve the solution time with only a small deviation from optimality.Wong Chi Fat."May 2007."Adviser: Janny Leung.Source: Dissertation Abstracts International, Volume: 69-01, Section: B, page: 0596.Thesis (Ph.D.)--Chinese University of Hong Kong, 2007.Includes bibliographical references (p. 256-270).Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web.Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web.Abstract in English and Chinese.School code: 1307