Vehicle Routing Problem

Disruption management of the vehicle routing problem with vehicle breakdown

This paper is a shortened version of the paper published as Disruption management of the vehicle routing problem with vehicle breakdown, Journal of the Operational Research Society (2011) 62, 742–749. doi:10.1057/jors.2010.19; published online 21 April 2010.The authors were Q M, Z Fu, J Lysgaard and R Eglese.

The full paper is available online on this site to members of the OR Society.

Abstract

This paper introduces a new class of problem, the disrupted vehicle routing problem (VRP), which deals with the disruptions that occur at the execution stage of a VRP plan. The paper then focuses on one type of such problem, in which a vehicle breaks down during the delivery and a new routing solution needs to be quickly generated to minimise the costs. Two Tabu Search algorithms are developed to solve the problem and are assessed in relation to an exact algorithm. A set of test problems has been generated and computational results from experiments using the heuristic algorithms are presented.

Introduction

Many procedures have been developed to produce optimal or near optimal solutions to vehicle routing and scheduling problems where demands and travel times are known and fixed. However, no matter how good a plan is, various disruptions may take place at the execution stage, which can make the plan no longer an optimal or even a feasible solution. Disruptions during the execution of a vehicle routing problem (VRP) plan may be caused by vehicle breakdowns, traffic accidents blocking one or more links, delayed departures from the depot or any service point, new orders or cancelled orders, etc. When a disruption occurs, routes should be quickly revised to minimise the negative effect it may cause to the delivery company and their customers. In practice, plans may be revised manually based on people's past experiences or common sense. Dealing with disruptions is a complicated decision-making process; therefore a decision support system with effective algorithms, which can quickly find a new routing plan when disruptions occur, is valuable.

The disrupted VRP problem is different from the classic VRP because:

1. In the original problem, vehicles depart from the depot and end at the depot. The goal is to design a set of minimum cost routes, originating and ending at the central depot. When a disruption happens, vehicles are at different locations. An optimal routing solution has to be found for vehicles that are starting from different locations and end at the depot. Therefore, the sub-routes can be open ones, not closed ones as they were in the original problem. However, a disrupted VRP is not exactly an open VRP problem as both ends of each vehicle route are fixed once disruption occurs.
2. Computing time. When a disruption occurs, it is critical to respond quickly with a new plan. This means while it is possible to spend hours or possibly days to find a high quality solution for the original problem, disruption management requires a quick response and thus a short computing time. As there is a clear trade-off between the computing time and the quality of the solution, an algorithm should be developed with a good balance between the two.
3. The original problem is solved from scratch. To solve the new problem, benefit will be taken from the solution to the original problem. First, this will make it quicker to find the new routing solution. Second, this may help minimise the deviation from the original plan. Deviation from the original plan may cause service delay or drivers’ overtime work. Change of plan may also cause issues if drivers are not familiar with new routes assigned.
4. Objectives. The objective of the original problem is usually to minimise the total operations costs involved. When a disruption occurs, there may be additional costs to take into account (eg cost of delay on delivering an order) and the inconvenience to the customers and drivers (eg waiting time, deviation from the original plan).
5. Decision making. In the situation when disruptions happen, it may be desirable to generate multiple solutions for the decision maker to choose from. Sometimes violations of customer requirements or other constraints are unavoidable when unexpected disruptions happen. Decisions may need to take account of issues that are not easily quantifiable. Several alternative good solutions may better support a manager's decision making. The original problem does not usually involve multiple solutions.

In this paper, we propose a formulation for one type of the disrupted VRP that involves a vehicle breakdown. Two Tabu Search algorithms are developed to solve the disrupted VRP. The algorithms focus on 1, 2 and 3 in the above list. Issues in 4 and 5 are not explored, that is we will not consider the multi-objective approach to the disrupted VRP in this paper. It should be noted that although we consider making use of the original plan as discussed in point 3 above, minimising deviation from the original plan is not an objective for the problem discussed in this paper. A set of test problems has been generated based on standard VRP benchmark problems and computational results from experiments using the heuristic algorithms are presented.

Problem description

The problem addressed in this paper is based on the Capacitated Vehicle Routing Problem (CVRP). In this case, the disruption involves a vehicle vi that breaks down at time t after leaving the depot and before delivering to the final customer on its route. We only look at the case where one vehicle breaks down because it is unusual to have more than one vehicle breaking down on the same day. In this situation, a number of unserved customers have to be reallocated to other vehicles. Extra vehicles (EVs) may have to be used to finish serving all the customers. The objective of this disrupted VRP is (1) to minimise the number of vehicles used and (2) to minimise the total distance travelled by all the vehicles after disruption happens to finish the delivery to the unserved customers. Priority is given to the number of vehicles. Therefore, a solution with fewer vehicles will always be better than a solution with more vehicles. For those solutions with the same number of vehicles, the one with the minimum total travel distance is preferred. The following assumptions have been made:

1. One EV is available in the depot. As has already been discussed, we assume that a solution that does not require the use of an EV is always better than the one that requires an EV.
2. A vehicle cannot be diverted until it has visited its current destination. This assumption is made because it is not easy to estimate the time required for finding the new plan and the communication with drivers. Therefore, in the new routing plan, the starting point for each vehicle that has not broken down is its next visiting point in the original plan.
3. The commodity that the vehicles are delivering is a single commodity that is transferable between customers, such as gas or oil. This means any vehicle is able to serve any customer as long as it is carrying enough to satisfy the customer requirement.
4. Each vehicle departs with full capacity.
5. The cost of the distribution is proportional to the distance travelled. No extra costs are involved.
6. All the vehicles depart from the depot at the same time 0 and we assume that all the vehicles are travelling at the same speed, that is one unit of distance per unit of time.
7. There are no time window constraints for any of the orders.
8. When a vehicle breaks down, if another vehicle is serving a customer, that customer is the starting point of its new route.
9. If a vehicle breaks down when it is serving a customer, this customer will not need to be visited by another vehicle.
10. If a vehicle has already returned to the depot when another vehicle breaks down, reuse of that vehicle should be seen as using an EV.

We shall refer to this problem as defined above as the Disrupted Capacitated Vehicle Routing Problem with Vehicle Breakdown (DCVRP-B).

The algorithms

We develop two metaheuristic algorithms to solve the DCVRP-B because the problem is NP-hard, and there is a time constraint on finding a new routing plan. Both algorithms are based on Tabu Search due to its effectiveness in solving VRPs.

Algorithm I

When a vehicle breaks down, an easy alternative plan is to send another vehicle from the depot to complete the route that the broken-down vehicle has not finished. The rest of the vehicles will keep following the original plan. As the original plan already gives the best possible routes, we base our initial solution on it to save computing time when finding the new solution to the disrupted problem.

Before developing an initial solution, it is necessary to check whether it is possible to complete serving all the customers without using the EV. This is done by comparing the total demand required for the unserved customers and the total load carried by the unbroken vehicles. We use different approaches to obtain the initial solution for these two different cases.

For those problems where an EV must be used, the initial solution is the same as the easy alternative plan:

1. For the disrupted route, a vehicle is sent from the depot to serve the customer which the broken-down vehicle was going to serve next when it broke down. The vehicle will continue serving the rest of the customers following the same order as was specified in the original plan.
2. For the rest of the routes, the starting point for each route is the next customer that should be served according to the original plan when disruption happens. The vehicles will continue serving the rest of the customers following the same order as was specified in the original plan.

For those problems where the service can be completed without using the EV, we have used an insertion algorithm to find the initial solution. The routes that do not involve a broken-down vehicle are formed in the same way as in the previous case. Assume EVs are not available. The unserved customers in the disrupted route will be inserted into the closest routes according to their distance to the midpoint between the starting point and the depot. If an insertion violates the capacity constraint, the customer should be inserted into the next closest route. If there is no feasible insertion route, the customer will be inserted into its closest route even though it is infeasible.

We have proposed a Tabu Search algorithm, which we believe is appropriate considering the characteristics of the DCVRP-B. It involves a small number of parameters and does not have any random element. It is simple, easy to implement, stable, flexible and finds a relatively good solution in a reasonable time.

The Tabu Search proposed starts from an initial solution, feasible or infeasible, and moves at each iteration to a best neighbourhood solution, until a stopping criterion is satisfied.

Algorithm II

Algorithm II is based on our TS heuristic presented for an open VRP. Its route is a closed one and the other routes are open ones (that is, one end of each route is at the depot and the other end is a customer location); otherwise all routes are open ones. In order to make Algorithm II quicker to find the new routing solution, the following modifications were performed on the previous TS heuristic:

1. In our previous TS heuristic, the initial solution is generated either randomly or by the farthest first heuristic. To take the benefit from the solution to the original problem, in Algorithm II, the initial solution is simply the same as the easy alternative plan.
2. The previous TS heuristic is able to deal with a route length constraint that does not exist in the DCVRP-B. Therefore, we relax this constraint by setting it to infinity.
3. The stopping criterion is changed to be a time constraint.
4. Some necessary changes are made for the TS heuristic to be capable of dealing with the mixed closed and open route situation.

Furthermore, compared with Algorithm I, this heuristic uses a different neighbourhood structure and randomly selects neighbours rather than searching a neighbourhood completely.

Results and findings

The program for Algorithm I was written in C# and Algorithm II was coded in Delphi 7.0. Both algorithms have been implemented on an Intel Core 2 Duo laptop running at 2.5?GHz with 4?GB of RAM. The test problems were adapted and selected from the standard CVRP problems. All these problems are Euclidean and it is assumed that the distance between each pair of customers is equal to the travelling cost. All the distances have been rounded to their nearest integer. For the instances in set A, both customer locations and demands are random. The instances in set B and M, however, are clustered instances. In the instances of set E and P, customer locations are uniformly distributed. The instances in set F are taken from real vehicle routing applications. The best known solution for each CVRP problem is used as the original routing plan before disruption. The direction of the vehicle on each route is the same as the best schedule given. For each test problem, different combinations of disrupted vehicle and disruption time were tested in the experiments. Because the average route length of the original routing plan for each of the test problems ranges from 83 to 164, three disruption times are created accordingly, which are either early (20), middle (40) or late (60) in the time required for a typical route. As route length varies in each problem and we choose the same disruption times for all test problems, in some cases, the proposed broken-down vehicle has already served all the customers in the route when the disruption happens. In this case, there is no need to reoptimise the problem, as the original solution will still be valid for the disrupted problem and any improvement found could have been applied to the original problem. Those invalid problems have been deleted from the problem set, which leaves 230 problems in total. For each problem, a time constraint of 60?s has been applied. For Algorithm II, the time constraint is 12?s and five runs are tested for each problem. The best result out of five is presented as the result obtained from Algorithm II within the time limit of 60?s.

Conclusions

We have described the DCVRP-B. Two heuristic algorithms based on Tabu Search have been presented. One is newly proposed for the problem (Algorithm I). The other is based on previous work using the open VRP formulation (Algorithm II). The algorithms take advantage of the original plan and a new routing plan can be found within a limited time. The newly proposed Tabu Search algorithm (Algorithm I) involves a small number of parameters and does not have a random element. The algorithm is simple, flexible and always gives a feasible solution. This algorithm outperforms Algorithm II and can also save a considerable amount of disruption cost compared to using an easy alternative plan. An exact algorithm has also been developed and it is able to find the optimal solution quickly in most of the cases, but in some cases fails to find a feasible solution within the required time limit. Algorithm I is able to find the optimal solution in all but 19 cases of the 230 problems tested. Although it is relatively harder for our algorithms to find optimal solutions for larger problems because of the time limit, more disruption cost savings can actually be obtained compared with using an easy plan.