Vehicle and manpower routing problems

Abstract

This thesis studies a set of vehicle and manpower routing problems for multitrip/ multiperiod planning, which can be widely applied in practice. Planning the routes of vehicles, e.g. trucks or ambulances, is usually applied in product and people transportation, while manpower routing occurs when scheduling field technicians to perform tasks at customer sites. Making an efficient and practical routing plan for vehicles and manpower can greatly affect the effectiveness and service levels of a company. Most existing literature on vehicle routing problems studies single period routing (e.g. a day), where the vehicles usually depart and return to the depot only once within the period, and the objective is to minimize the operational cost. However, this assumption may not satisfy other important business requirements, such as labor law regulation. Even when the planning is performed within a single period, the vehicles may depart and return to the depot multiple times. Therefore, more exible routing approaches that consider these factors (such as multiperiod and multitrip planning) are more likely to be practically applicable. The contributions of this thesis are threefold. First, we developed some effective algorithms to resolve real world routing problems for mulitrip and multperiod planning. Second, we introduce new variants of vehicle and manpower routing problems to the literature. Third, we contributed a set of real-world data to research community. The problems investigated in this thesis are all derived from the real world projects, namely an inspector routing problem in a major retail distributor, a periodic vehicle routing problem in one of the largest restaurant chains in Hong Kong, and a non-emergency ambulance transfer service in public hospitals in Hong Kong. The first problem studied in this thesis is an inspector scheduling problem for a major retail distributor. Most existing literature on variations of the vehicle routing problem assumes that all vehicles are in service within the entire planning horizon. However, this assumption may not be valid in practice for some applications due to working time regulations. We formulate the inspector scheduling problem as a multiperiod vehicle routing problem with profit (mVRPP), where the goal is to determine routes for a set of vehicles that maximizes the amount of reward collected from the visited locations, and the vehicles can only travel during working hours within each period in the planning horizon. Furthermore, the vehicles are only required to return to the depot at the end of last period. We propose an effective memetic algorithm with a giant-tour representation to solve the mVRPP. To efficiently evaluate a chromosome, we develop a greedy procedure to partition a given giant-tour into individual routes, and prove that the resultant partition is optimal. We evaluate the effectiveness of our memetic algorithm with extensive experiments on a set of modified benchmark instances. The results indicate that our approach generates high-quality solutions that are reasonably close to the upper bounds and significantly better than the solutions obtained using heuristics employed by human schedulers. We next study a periodic vehicle routing problem encountered by a restaurant chain in Hong Kong. To develop customer relationships and increase service efficiency due to familiarity, some companies prefer their service personnel to visit regular customers at approximately the same time each day when service is required. However, this type of service consistency may result in increased operational cost, especially when the customers' demands uctuate significantly day by day. In this paper, we investigate a variant of the periodic vehicle routing problem with time windows that includes a limited visiting quota constraint (PVRPTW-LVQ), which requires that any particular customer may be serviced by at most R different vehicles over the planning horizon. The objective is to first serve all customers with a minimum number of vehicles, and then reduce the total distance traveled. We formulate the problem as a mixed-integer linear program, and also propose a three-stage approach combining several search techniques for the problem. Extensive computational experiments on benchmark instances show that the proposed method outperforms previously published approaches for both the PVRPTW-LVQ and the consistent vehicle routing problem (ConVRP), which is a related problem where R=1. We also empirically examine the effects of varying levels of service consistency and demand uncertainty using our approach, which provides additional insights on the trade-offs between these two factors in terms of operational cost. The third problem we investigated is the non-emergency ambulance routing problem. This problem is derived from the non-emergency ambulance transfer service (NEATS) in Hong Kong public hospitals. The NEATS provides transportation service for disabled and elderly patients between hospitals and residences. The efficiency of the NEATS can greatly affect the operations of the hospital. We model this problem as a multitrip pickup and delivery problem with time windows (MT-PDPTW). We devised a fast heuristic to solve the problem, and performed experiments on various sets of data to evaluate the performance of the algorithm. We then tested the algorithm on real world data, which showed that our proposed algorithm can solve the problem quickly. We also discussed the relationship between service level and capacity in the NEATS system.

Date of Award	15 Feb 2012
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Leong Chye Andrew LIM (Supervisor)