Pickup and Delivery Problem with Loading Cost

Abstract

This thesis studies a class of pickup and delivery problem with loading cost (PDPLC), which has wide applications in practice. As an important branch of the classical vehicle routing problem (VRP), the pickup and delivery problem (PDP) has been extensively studied in the field of operations research for decades. The objective of the classical PDP is to find a set of routes for a fleet of vehicles with known capacity to serve a given set of pickups (the origins) and deliveries (the destinations) under various constraints, such as vehicle capacity, time window and maximum duration. In the classical PDP, the transportation cost is usually proportional to the travel distance, but is independent of the load of the vehicle. In practice, the Chinese expressways system applies the toll-by-weight scheme where the expressway tolls are levied according to the vehicle’s weight and its travel distance. The loading cost objectively increases the transportation cost and presents complexities and challenges to the vehicle schedule management of logistics companies. Therefore, this thesis studies a class of the PDPLC, where the cumulative cost structure is used to incorporate the loading cost in the objective, and the transportation cost of vehicles per unit distance is a function of the vehicle’s weight which is dynamic when the vehicle travels along the route.
The contributions of this thesis are fourfold. First, I introduce three practical new pickup and delivery problems with the loading cost, which are inspired by real world applications in logistics industry. Second, these problems are formulated into mathematical models and are comprehensively analyzed. Third, based on the models and its characteristics, effective and exact algorithms are proposed for the problems. Finally, comprehensive experiments of benchmark instances are conducted and detailed solution results are presented, which are expected to facilitate future researches of the related problems.
The first problem studied in this thesis is the One-to-One Pickup and Delivery Problem with Loading Cost (1-1PDPLC), which is the first PDP that takes the loading cost into consideration. The 1-1PDPLC involves taking decisions on a set of minimal cost routes, which comply with vehicles capacity constraint and maximal duration constraint, in order to satisfy a set of transportation requests. Each transportation request involves transporting goods from a pickup node to the corresponding delivery node. A branch-and-cut algorithm and a branch-and-price algorithm are proposed. In the branch-and-price algorithm, I devise an ad hoc label-setting algorithm to solve the pricing problem and employ the bounded bidirectional search strategy to accelerate the label-setting algorithm. The proposed algorithms were tested on a set of instances generated by a common data generator stated in literature. The computational results show that the branch-and-price algorithm significantly outperforms the branch-and-cut algorithm, and the former can solve most of the instances to optimality within a reasonable time frame.
The second problem is the Selective Pickup and Delivery Problem with Loading Cost and Time Window (SPDPLCTW), which is a new variant of the PDP in a many-to-many commodity structure. In the SPDPLCTW, a fleet of vehicles is dispatched to serve a set of customers under the restrictions of the vehicle capacity, maximum duration, and time window. As the customer requests must be satisfied in the SPDPLCTW, each delivery is served once. Similar to the VRP, the depot is assumed as a pickup with unlimited storage and if necessary, vehicles depart from the depot with an initial load to fulfill the deliveries. Pickup is only visited when adding the load of the pickup can save transportation cost. To solve this problem, I propose a branch- and-price-and-cut algorithm. An ad hoc label-setting algorithm with a linear structure is devised, where the tabu heuristic is employed to accelerate the label-setting algorithm. The experiment instances are generated by a designed data generator, and computational results show that the proposed algorithm can handle most instances efficiently.
The third problem is the Split Load Pickup and Delivery Problem with Loading Cost and Time Window (SLPDPLCTW), which is a new variant of the PDP that considers the constraints of vehicle capacity, maximum duration and time window. The SLPDPLCTW involves decisions on a set of minimal cost routes to satisfy the demand of all deliveries, where each delivery is visited only once. In order to collect commodities to fulfill deliveries, the loads of pickups can be separately collected by different vehicles but the total quantity of commodities collected from a pickup cannot exceed its supply. A branch-and-price-and-cut algorithm is devised to solve this problem. I first prove the optimal solution of the pricing problem is an extreme pickup pattern of the route. Further, a tailored label-setting algorithm with a piece-wise linear structure is designed and a bounded bidirectional search strategy is employed to accelerate the label-setting algorithm. The arc-flow inequality is applied due to the propriety of the problem. A set of instances are generated by a designed generator and a comprehensive instance analysis is conducted. The computational results show that when the pickup supply is large enough, the proposed algorithm can solve most instances efficiently.

Date of Award	10 Oct 2017
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Leong Chye Andrew LIM (Supervisor), Guangwu LIU (Supervisor), Jue GUO (External Supervisor) & Leong Chye Andrew LIM (External Co-Supervisor)