Multi-Objective Vehicle Routing Problem: Case studies in retail distribution

  • Raza Khan

Student thesis: Phd


Vehicle routing and scheduling are fundamental problems encountered in retail distribution, in the context of both primary and secondary distribution. For the purpose of primary distribution, the services of third party logistics companies (3PL) are usually acquired. In contrast, the secondary distribution is generally performed using a fleet of in-house vehicles. The optimization of distribution at both levels is challenging and realistic routing plans may often require the consideration of multiple, conflicting objectives, and the identification of a suitable compromise solution.In this thesis, two real-world case studies are considered that can be formulated as special cases of the vehicle routing problem (VRP). One of these is about the primary distribution carried out by a 3PL company; while the other relates to secondary distribution in an urban context. The two cases differ significantly in the structure and the details of the problem modelled, but the overall underlying aim is the same, i.e. to transport goods as efficiently as possible and thus improve customer service, which is critical for long-term sustainability. The first case study focuses on inter-depot trunking carried out by a 3PL company that operates a network of depots in the UK. Salient features of this problem include paired pickup and delivery points, adjustable compartment space, and the swap of trailers between vehicles. As independent plans are currently generated by human planners who are based at different depots, the resulting overall plan is typically suboptimal. VRPs in such a network-based operations context have been given very little attention in the literature. Here, a linear programming model is proposed that takes into account the entire network when generating routing plans. Results show that this centralized approach has the potential to lead to significant savings in terms of the vehicles used, the distance travelled and CO2 emissions. Furthermore we show that the choice of objectives has a significant impact on the structure of the routes suggested.The second case study pertains to delivery plans in an urban context and, specifically, routing under time-varying congestion. As travel speed varies and is time-dependent, plans that are generated by considering constant speeds become unreliable in terms of time-estimation and may lead to the violation of time-window constraints. In this work, multiple objectives (distance, time, CO2, equity among drivers, fleet size and customer satisfaction) are considered simultaneously while historical speed information is used as a proxy for the time-varying congestion in the road network. A hybrid, GA-based interactive optimisation method is developed that takes into account the planner's aspiration levels and weights for different objectives through several iteration cycles in order to guide the search process and reach a most preferred solution.
Date of Award1 Aug 2016
Original languageEnglish
Awarding Institution
  • The University of Manchester
SupervisorJian-Bo Yang (Supervisor) & Julia Handl (Supervisor)


  • trailer swap
  • interactive VRP
  • multi-objective vehicle routing problem

Cite this