Abstract: This paper introduces the vehicle routing problem of the vaccine delivery with vehicle breakdowns. In the delivery process of vaccines, a continuous low-temperature environment is required. Once any event that causes the temperature to rise happens during the whole process, the quality of vaccines cannot be assured, and even human lives that are injected by the vaccines are threatened. Therefore, this paper presents a method to evaluate the reliability of vehicle routing schemes in the vaccine delivery with vehicle breakdown. The method adopts the simulation idea and supposes breakdowns at every fixed time interval for each vehicle. When a supposed vehicle breakdown happens, a saving-based heuristic will be applied to generate a rescue scheme. Finally, the method was coded and run on one of the classical CVRP instances.Keywords: simulation-based method, reliability of vehicle routing scheme, vaccine delivery, vehicle breakdown
Vaccine is a very important strategic products for a nation. It plays an important role in the protection of people’s health and the avoidance of health risks. But vaccines are very particular in their production and delivery process, in which a continuous low-temperature environment is required. Therefore, a cold chain is often used to ensure the low-temperature condition for vaccines. The cold chain must not be interrupted from the initial producion to the final injections for humans. Once there is any interruption during the whole process, the temperature will rise, the quality of vaccines cannot be assured, and even human lives that are injected by the vaccines are threatened. Thus a continous cold chain is very important for the quality of vaccines.To ensure the low-temperature condition, the Chinese government has introduced a series of strict regulations to the production process of vaccines. But surprisingly, the delivery process of vaccines is not well Supported by the National Natural Science Foundation of China (70801008, 71271037), the Fundamental Research Funds for the Central Universities (DUT12JR09) and the Foundation of Liaoning Educational Committee (L2012019)managed and controled, which leads to a great risk of quality loss of vaccines. Under the uncertain delivery environment, there are many possibilities that the low-temperature conditions for vaccines are interrupted and vaccines have to be exposed to a high-temperature environment. When any interruption event occurs, a good delivery scheme can be easily adjusted so that vaccines will not be exposed to high-temperature environment or will not be exposed too long, while a bad scheme cannot. Therefore, the reliability of a delivery scheme for vaccines is very important in coping with the uncertainties of delivery processes of vaccines. And how to evaluate the reliability of vehicle routing schemes in vaccine delivery comes to be an important problem which are studied in this paper. Although there is almost no direct research on the reliability of vehicle routing schemes in vaccine delivery, some related studies still exist, which provide us with a good research base. The representative studies include the following two aspects: the studies on cold chain logistics and disruption management of vehicle scheduling problem. On the cold chain logistics, Osvald and Stirn  developed an algorithm for the distribution of fresh vegetables in which the perishability represents a critical factor; Hsu et al.  extended a vehicle routing problem, with time-windows (VRPTW) by considering the randomness of the perishable food delivery process and constructing a SVRPTW model to obtain optimal delivery routes, loads, fleet dispatching and departure times for delivering perishable food from a distribution center; Chen et al.  propose a nonlinear mathematical model to consider production scheduling and vehicle routing with time windows for perishable food products in the same framework. Other studies like references [4-9] also concern the model and algorithm of the cold chain logistics. On the disruption management of vehicle scheduling problem, Lorini et al.  extended a previously developed problem-solving approach for a vehicle routing problem with dynamic requests and dynamic travel times to account for more sophisticated communication means between the drivers and the central dispatch office; Li et al.  introduced and studied real-time vehicle rerouting problems with time windows, applicable to delivery and/or pickup services that undergo service disruptions due to vehicle breakdowns; Mu et al.  focused on disruption management of the vehicle routing problem, in which a vehicle breaks down during the delivery and a new routing solution needs to be quickly generated to minimise the costs, and developed two tabu search algorithms to solve the problem. Other studies like references [13-19] also concern the model and algorithm of the disruption management of vehicle scheduling problem. As a result of the possibilities of vehicle breakdowns in the vaccine delivery, this paper focuses on evaluating the reliability of vehicle routing schemes in vaccine delivery when vehicle break down during their delivery process. This is a challenging problem that has never been studied before. To evaluate the reliability of a vehicle routing scheme, a simulation-based method is presented in this paper. The remainder of this paper is arranged as follows. First, the problem studied in the paper is described in the next section. And the framework of the evaluation method is presented in the Section 3. An experiment is reported in Section 4, and the paper finishes with the conclusions.