This thesis studies a class of vehicle routing problem with pickup and delivery (VRPPD) that has wide applications in practice. The vehicle routing problem (VRP) has been a hot research topic in the field of operation research for more than five decades. It can be described as the problem of finding a set of routes for a fleet of vehicles with known capacities to visit a given set of customers while minimizing the total cost, the travel time, or the number of vehicles. In addition, various constraints must be satisfied, such as vehicle capacity constraint, time window constraint, travel duration constraint, and so on. In the VRPPD, the vehicles are required to serve the customers, each involving pickup and/or delivery requests, which indicates that the qualities of each vehicle are fluctuate as the vehicle travels along the routes. Thus, the VRPPD is a generalization of the classical VRP. The VRPPD has received increasing attention in recent years due to its wide applications to many distribution systems. One interesting example is the application to fast-fashion retailing, in which each location requires replenishment according to its inventory and forecast demand. From the optimization perspective, products can be swapped between locations to reduce the travel cost. Thus, each location has both pickup and delivery requests.
This thesis has four main contributions. First, we introduce two new vehicle routing problems motivated by an international fast-fashion retailer–Charles and Keith (CK). Secondly, we formulate these problems into different mathematical models. Thirdly, we develop effective solution programming procedures based on the models for these problems. Lastly, we test our solution procedure based on real data and provide a large number of results, which can facilitate future research on these and related problems.
The first problem in this thesis is the multi-commodity pickup and delivery problem (m-PDP), which is a generalization of the VRPPD that considers multiple and varied commodities that require picking up from and delivering to each store. In this problem, the shortage of commodities at each store must be replenished, and the any leftover stock must be transported to the warehouse or to other stores where it is needed. The retailer provides a set of homogeneous vehicles with known capacity to satisfy the requests. Each store can be visited at most once by a single vehicle. The objective is to minimize the total traveling cost. We introduce a mixed integer linear programming model and implement a branch-and-price-cut algorithm to solve this problem optimally. Experiments demonstrate that the branch-and-price-cut algorithm can solve the instances efficiently. In addition, we also developed a heuristic method to solve the m-PDP, including a construction procedure and a tour improvement procedure. We applied three different construction heuristics to find initial solutions. A tour improvement algorithm based on the variable neighborhood search (VNS) method is introduced. Finally, the computational results show that our heuristic is able to obtain a near optimal solution with much less computation effort than the branch-and-price-and-cut algorithm.
The second problem is the multi-commodity pickup and delivery problem with inventory scheduling (m-PDPIS), which is an extension of the first problem by considering inventory holding cost of each store and warehouse. In this problem, the stores provide or require known amounts of m different commodities, and each vehicle has a known capacity. Each store can be visited at most once by one vehicle to serve its demands. It is assumed that a unit of commodity collected from a store can be supplied to any other store where it is required. Unlike the first problem, the commodities are allowed to remain at the store by considering the inventory cost and store capacity. The objective is to minimize the total cost, including the vehicle traveling cost, store inventory cost, and depot operation cost. We introduce a mixed integer linear programming model for the m-PDPIS, describe valid inequalities to strengthen the linear programming relaxation of the model, and detail separation procedures to develop a branch-and-cut algorithm. Finally, computational experiments are shown.