Information Technology Reference
In-Depth Information
Feasibility Analysis
There is not guarantee that, in a given iteration of the algorithm the final solution
delivered be feasible. Therefore it becomes important to assess the success rate
of the heuristic in terms of its feasibility. To this end, we proceed to compute
the percentage of times a feasible solution was obtained per iteration, and, given
the algorithm returns the best solution found over all iterations, the percentage
of times the algorithm delivered a feasible solution.
Table 1 shows the results for the different data sets. Columns 2-3 indicate the
average and maximum success rate per iteration over all instances tested. The
last column shows the success rate of the entire heuristic. As can be seen, even
though some individual iterations may fail, it is empirically observed that the
heuristic is always successful.
Tabl e 1.
Feasibility success rate (%)
Per iteration Per algorithm
Data set Ave Max
execution
Small
99.6 100.0
100.0
Medium 68.0 100.0
100.0
Large
60.0 100.0
100.0
Comparison with Current Practice
Finally, we present a comparison between the solution found by our heuristic
and the solution reported by the firm in a particular case study.
Tabl e 2.
Comparison between current practice and proposed heuristic
NV NVS NVD NT
RC
FC
Total cost
Firm solution
47
9
38 85
$186,018 $70,500 $256,518
Heuristic solution 50
28
22 72
$167,020 $75,000 $242,020
Table 2 shows this comparison itemizing the individual costs and vehicle us-
age, where NV, NVS, NVD, and NT stand for number of vehicles, single vehicles,
double vehicles, and trailers used, respectively. RC and FC are the routing and
fixed cost, respectively, and the last column is the total solution cost. The re-
duction of the heuristic solution is about 6%. It can be seen this is due in great
deal to a better arrangement of the single and double vehicles. The new solu-
tion uses 3 more vehicles; however, the main difference comes from the number
of single- and double-vehicles used. The new solution uses more single-vehicles
which yield lower traveling costs overall. It is clear the contrast with the current
practice where it was firmly believed that using fewer vehicles (i.e, more double
vehicles) would be a better choice.
5 Conclusions
In this paper we studied a vehicle routing problem with pickup and delivery
from a real-world application in a bottled-beverage distribution company. Given
