vaccine delivery with vehicle breakdown
This paper focuses on the evaluation method for the reliability of vehicle routing schemes in the vaccine delivery with vehicle breakdown. The vehicle routing problem in the vaccine delivery with vehicle breakdown can be described in the following.Let G = (V, E)be a graph where V = {v0, v1, …, vn} is the set of customer nodes {v1, …, vn} and depot node v0 and E = {(vi, vj): vi, vj∈V, i≠j} is the set of edges. Each customer node vi (i=1…n) is associated with a positive demand qi of the same kind of vaccine. Each edge (vi, vj)∈E (i≠j)is associated with a positive travel time tij. Define K as a set of identical refrigerator vehicles available to deliver goods from the depot to the customers. Each vehicle has the same capacity C(C>>max{qi/1≤i≤n}). Some additional constraints associated with the problem are as follows:(1) Each vehicle can perform only one route in a scheduling period (e.g. a day).(2) Each customer node can be visited only once by exactly one vehicle.(3) All vehicles begin and end their routes at the depot node v0. (4) No vehicle can be loaded exceeding its maximum capacity C. (5) When vehicles execute their initial routing plan, one of them breaks down and the vaccines in it has to be exposed to the outside environment which may be in high temperature and not fit for vaccines. The vehicle has to be rescued otherwise the vaccines in the vehicle will be deteriorate with time elapsing. Therefore, we can reasonably assume a period of time PT, beyond which vaccines will lose their effectiveness. To be more precise, if vehicle i breaks down at the time T1 and is rescued at the time T2, formula (1), where Lost_Cost stands for the lost cost of vaccines in the vehicle that has broken down, is true: >ic q T2 T1+ PTLost_Cost0T2 T1 PT×=≤+(1)The above formula indicates that if rescued in the period of PT, quality of vaccines will not get worse and thus the cost does not lose, but if not rescued timely, the vaccines cannot be used and thus the cost lost is icq×, where c is used to transfer vaccine quantity to cost. (6) A vehicle routing scheme with higher reliability can cope with any event of vehicle breakdowns in low rescue cost, while on the contrary, a scheme with lower reliability has to spend much more costs to cope with vehicle breakdown event. Therefore, the reliability of a vehicle routing scheme can be regarded as the rescue cost for a scheme to cope with the event of vehicle breakdowns. Thus the reliability of a scheme can be defined as formula (2), where Routing_Cost stands for the routing cost of the rescue scheme and Initial_Coststands for the routing cost of the initial scheme. As defined in formula (3), the rescue cost is the sum of the lost cost and the routing cost._ __(1)100%___100%__Lost Cost Routing Cost Initial CostReliabilityLost Cost Routing CostInitial CostLost Cost Routing Cost+−=−×+=×+ (2)___Rescue CostLost Cost Routing Cost=+(3) Suppose the possibilities of breakdowns of each vehicle at any time point are equal, in other words, it is a uniform distribution. And the presented evaluation method is mainly used to calculate the reliability of a scheme
3 Experiments
In this section, we present a computational result of the simulation-based evaluation method, which has been coded in Java and run on a laptop with an Intel® Core™2 Duo CPU T7100 at 1.8GHz, 2 GB RAM, and the Microsoft Windows XP operating system.
The evaluation program was run on two of the classical Capacitated Vehicle Routing instances, A-n32-k5 and A-n37-k5, and the details of the instances can be found at http://www.branchandcut.org/. The best-known solution of A-n32-k5 and A-n37-k5, which also can be found at the website, was evaluated by the presented method in this paper. The preliminary experiments showed a satisfactory performance when the parameter values were set to c=10, PT=10, and ti=5.The average rescue cost and the reliabilities of the two instances are given in Tab.1, where the three columns represent the instance names, the rescue costs, and the reliabilities of the two instances respectively. From Tab. 1, we can observe that the reliabilities of the two instances are 59.8% and 67.3% respectively. In conclusion, the “so-called” best-known solutions aim at minimizing the routing cost of a scheme but have poor abilities to cope with unexpected vehicle breakdown events despite of their low initial routing costs, and invaccine deliveries, the reliability is a very important index in distinguishing good ones from routing schemes.
4 Conclusions
This paper focuses on the problem of evaluating the reliability of vehicle routing schemes in the vaccine delivery with vehicle breakdown and presents a simulation-based method for it. The method, which does not require complex fine-tuning processes, combines the classical Clarke and Wright heuristic with Monte Carlo simulation and provides a relatively simple and yet flexible solution procedure for evaluating the reliability of vehicle routing schemes. According to the objective of the problem, the presented method changes the saving definition of the classical Clarke-Wright algorithm and makes it fit for the problem which requires large amount of computation. The method is applied to classical Capacitated Vehicle Routing instances and the computation result demonstrates its validity.
