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
Problem description
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
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.
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.
