Vehicle routing problems with cumulative cost structure

Abstract

This thesis studies a class of vehicle routing problems with cumulative cost structure(VRPCCS), which have wide applications in practice. Vehicle routing problem (VRP) has been a hot research area in the field of operations research for more than five decades. It consists of finding a set of routes for a fleet of vehicles with known capacities to service a given set of customers while minimizing the total travel cost and satisfying various constraints, such as capacity constraint, time window constraints and maximum travel distance constraints. Unlike the classical cost structure where the travel cost is only proportional to the travel distance, the cumulative cost structure defines the travel cost of vehicles per unit distance as a function of another quantity (e.g., number of customers served, weight of vehicle) which accumulates as the vehicle travels along the route. From the perspective of modeling, the VRPCCS is a generalization of the classical VRP. Compared to the classical VRP, the VRPCCS has received increasing attention in the literature in recent years due to its applicability to many distribution systems. Some cumulative cost structures, e.g. the customer waiting time, are considered in the customer-centric or service-based objective functions for increasing the level of customers' satisfaction. Another interesting example of the cumulative cost structure arises in Chinese expressway system where expressway tolls are levied according to vehicle weight and traveling distance, which is referred to as toll-by-weight scheme. The contributions of this thesis are fourfold. Firstly, we introduce three new and practical vehicle routing problems that take the cumulative cost structures into account to the literature. Secondly, we formulate these new problems into different types of mathematical programming models and conduct detailed and comprehensive analysis on their properties. Thirdly, based on the models and the properties we propose effective solution procedures for these problems, both in exact and heuristic ways. Lastly, we provide a large number of benchmark instances as well as detailed solution results, which facilitate the future researchers to investigate these or related problems. The first problem studied in this thesis is the multiple traveling repairmen problem with distance constraints (MTRPD), which is an extension of the multiple traveling repairman problem by considering a limitation on the total distance that a vehicle can travel. In the MTRPD, a fleet of vehicles is dispatched to serve a set of customers. Each vehicle that starts from and ends at the depot is not allowed to travel a distance longer than a predetermined limit and each customer must be visited exactly once. The objective is to minimize the total waiting time of all customers after the vehicles leave the depot. To optimally solve the MTRPD, we have implemented three branch-and-price-and-cut algorithms, which correspond to three types of label-setting algorithms applied to the pricing subproblem. Experiments show that the branch-and-price-and-cut algorithm that includes the bounded bi-directional label-setting algorithm and space state relaxation outperforms the other two algorithms, and is able to solve most of the test instances optimally. The second problem is called the split-collection vehicle routing problem with time windows and linear weight-related cost (SCVRPTWL), which is a new VRP variant that simultaneously considers time windows, split collection and linear weight-related transportation cost. This problem consists of determining leastcost vehicle routes to serve a set of customers while respecting the restrictions of vehicle capacity and time windows. The travel cost per unit distance is a linear function of the vehicle weight and the customer demand can be fulfilled by multiple vehicles. The SCVRPTWL can be viewed as a generalization of the classic split-delivery vehicle routing problem with time windows (SDVRPTW). To solve this problem, we propose an exact branch-and-price-and-cut algorithm, where the pricing subproblem is a resource-constrained elementary least-cost path problem. We first prove that at least an optimal solution to the pricing subproblem is associated with an extreme collection pattern, and then design a tailored label-setting algorithm to solve it. Computational results show that our proposed algorithm can handle both the SDVRPTW and our problem efficiently. The third problem is a VRP variant that incorporates stochastic demands and toll-by-weight scheme, which is therefore named the vehicle routing problem with stochastic demands and toll-by-weight scheme (VRPSD-TBW). We deal with this problem using a priori optimization solution strategy with dynamic recourse, where the key of the solution procedure is to compute the expected cost of a given route. The problem aims to design a set of collection routes with minimal total expected travel cost to fulfill the requests of a set of customers. In order to find the set of best vehicle routes, we propose an adaptive large neighborhood search (ALNS) algorithm that employs several approximate evaluation schemes for the expected cost of the route and several removal and insertion heuristics. Experiments on a set of benchmark instances which are generated based on the information from the real data in several Chinese provinces demonstrate the effectiveness of our ALNS algorithm.

Date of Award	15 Jul 2014
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Chi Hang Stephen LEUNG (Supervisor) & Leong Chye Andrew LIM (Supervisor)