Team # 38411 Page 13 of 28

4.3.1 Improved Simulated Annealing(ISA)

Simulated annealing (SA) is a method for solving unconstrained and bound-constrained optimization problems. The method models the physical process of heating a material and then slowly lowering the temperature to decrease defects, thus minimizing the system energy[10][11].

The traditional simulated annealing algorithm simply to consider the spatial distance. Before solving the shortest path, we need to do some preparation. Data in the Table 6 is the latitude and longitude data, we first convert it to facilitate spatial distance operations. ● Spatial distance formula:

Set A, B geographic coordinates as?x1,y1?, ?x2,y2?. Inferior arc from point A to point B is actual distance between two points. Set the geocentric as coordinate origin and construct dimensional Cartesian coordinate system. Then, rectangular coordinates is

A?Rcosx1cosy1,Rsinx1cosy1,Rsiny1?,B?Rcosx2cosy2,Rsinx2cosy2,Rsiny2?, (4.3.1)

whereR?6370is radius of the earth. Actual distance A, B two points is

?OA?OBd?Rarccos??OA?OB?????.

Simplification is

(4.3.2) (4.3.3)

d?R?arccos??cos?x1?x2?cosy1cosy2?siny1siny2??.

● Simulated annealing algorithm is described as follows: (1) Solution space.

Solution space can be expressed as?1,2,?,18,19?. (2) The objective function.

The objective function for all target reconnaissance path length. Final goal is

minf??1,?2,?,?19???d?i?i?1,

i?119 (4.3.4)

where: ?i?j means reconnoiter target j in i-th times; an initial solution is?1,2,?,19?. (3) Generate new solution.

Assume previous iterations of solution is (?1??u?1?u?u?1??v?1?v?v?1??w?1?w?w?1??19). Then, u and v are randomly selected, and exchange the order into reverse, a new path is?1??u?1?v?v?1??u?1?u?v?1??19.

Next, u, v and w are randomly selected, and the path between U and V is inserted behind w. The new path is?1??u?1?v?1??w?u??v?w?1??19.

(4) The difference between the cost function.

?f?d?u?1?v?d?u?v?1?d?u?1?u?d?v?v?1????.

(4.3.5)

(5) Acceptance criteria.

Team # 38411 Page 14 of 28

?f?0??1,P??

exp??f/T.?f?0????(4.3.6)

If ?f?0, we accept new path directly; If not, we accept new path with the probability of

exp???f/T?.

(6) Drop temperature.

Drop temperature by coefficient of temperature drop ? selected. Then, the new temperature T equals to ?T(T is previous iterations of temperature; we choose ? equals to 0.999.

(7) Termination condition.

When current temperature reach the termination temperature e?10?30, annealing process is ended. If T?e, annealing process is ended and print out current status.

4.3.2 Analysis of Result

To simplify the data, we consider that starting the 1st logistics point, then travel all the logistics points, finally back to the 1st logistics point. Of course, we can also calculate the shortest path between two arbitrary logistics points, but we do not intend to do that, because of the limited length of the article.

Because simulated annealing algorithm is a random intelligent algorithm, Matlab calculated four random path is as follows:

1010998Latitude8Latitude77665547891011Longitude1213144

107891011Longitude121314

(1)

10 (2)

9988LatitudeLatitude77665547891011Longitude1213144

7891011Longitude121314

(3) (4)

Figure 6. Distribution route optimization.

The four figures above shows random optimization route calculating by annealing algorithm, and the total logistics distance respectively is 2079.0km, 2075.2km, 2076.3km, 2073.5km.

Team # 38411 Page 15 of 28

To make it more intuitive, even in extreme cases, it takes only 10 hours to pass through every logistics point if we fly by UH-60 Blackhawk helicopter (cruising speed 200km/h).

What if we don’t have the shortest routes algorithm? Diesel must be a huge expense. Furthermore, never forget those dying patients. Your time is their lives.

4.3.3 Sensitivity to Parameters

In order to measure the stability of the simulated annealing algorithm, we selected the distribution of vaccine research laboratory data to find the shortest path vaccine deliveries. The data attach to Table 7, we can see that they are functional and their latitude, longitude. What’s more, we assume that every LabOwner is friendly, nothing to do with their LabShortName.

Table 7. Vaccine research laboratory distribution.

ID 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 LabShortName Nigeria EU Mobile Lab US-CDC Lab OIC-NMRC Mobile Lab, Montserrado USAMRIID OIC-NMRC Mobile Lab, Bong PHA Canada (Magburaka) EU Mobile Lab, Hastings China-CDC Lab NICD South Africa Lab EU Mobile Lab, Gueckedou Institut Pasteur Dakar (Conakry) PH England Mobile Lab, Western Rural PH England Mobile Lab, Port Loko US 1st Area Medical Laboratory, Zwedru US 1st Area Medical Laboratory, Tappita US 1st Area Medical Laboratory, Saniquelle PH England Mobile Lab, Bombali Rospotrebnadzor Mobile Lab US-CDC Lab IP Lyon Mobile Lab US 1st Area Medical Laboratory, Greenville Italy Mobile Lab US DTRA Belgium Mobile Lab (N’LabOwner Nigeria Mobile Lab CDC Atlanta USA Liberia National Public Health Lab (supported by USAMRID) USA Public Health Agency Canada EU Consortium China National Institute for Communicable Diseases, South Africa EU Consortium Guinea National Public Health Lab Supported By IP Dakar PHE Porton Down PHE Porton Down USA DoD USA DoD USA DoD PHE Porton Down Russian Federation CDC Atlanta Institute Pasteur Paris US DOD National Institute for Infectious Diseases \US DTRA Centre for Applied Molecular Status Functional Functional Functional Functional Functional Functional Functional Functional Functional Functional Functional Functional Functional Functional Functional Functional Functional Functional Functional Functional Functional Functional Functional Functional Latitude -13. 2439 -10. 6966 -10. 7869 -10. 3577 -9. 47709 -11. 9486 -13. 1348 -13. 1495 -13. 265 -10. 1211 -13. 6832 -13. 0881 -12. 7862 -8. 13641 -8. 86012 -8. 71312 -12. 1064 -13. 3875 -11. 7321 -9. 46588 -9. 03847 -13. 2781 -12. 4861 -8. 81549 Longitude 8. 489305 6. 24016 6. 384793 6. 529713 7. 005815 8. 779162 8. 402994 8. 386861 8. 403 8. 55323 9. 535421 8. 269012 8. 766011 6. 057502 6. 509969 7. 362422 8. 933787 9. 706308 7. 957269 8. 518399 5. 009736 8. 423611 8. 103168 7. 751143 Team # 38411 Page 16 of 28

Zerekore) 25 26 Dutch Mobile lab Dutch/IOM Technologies (CTMA) Université catholique de Louvain (UCL) & Defense L Laboratory for Infectious Diseases and Screening, Centre for Infectious Disease Control, RIVM MoH (donated to MoH) Functional Functional -10. 7 -11. 1368 8. 591352 6. 820856 Note: Data comes from Financial Track Service.

We calculate the shortest distance and draw follow charts by Matlab:

109.598.58109.598.58LatitudeLatitude7.576.565.55891011Longitude1213147.576.565.55891011Longitude121314

109.598.58

109.598.58 (1) (2)

LatitudeLatitude7.576.565.55891011Longitude1213147.576.565.55891011Longitude121314

(3) (4)

Figure 7. Laboratory path optimization.

The four figures above shows random optimization routes calculating by annealing algorithm, and the total laboratory paths respectively are 2065.9km, 1997.1km, 2000.4km. By applying the simulated annealing algorithm, the total length of the laboratory path between laboratory points will reach an optimum value, thus greatly reducing delivery time and realizing the high-efficient resource sharing.

For our part, we are very fond of this algorithm because it is suitable for almost all paths optimized for robustness. For example, it can be used in the laboratory’s vaccine distribution optimization, optimization of logistics distribution center, the National Rescue Team distribution optimization and so on.