 Open Access
 Total Downloads : 101
 Authors : Valeriy Sirokurov
 Paper ID : IJERTV4IS040228
 Volume & Issue : Volume 04, Issue 04 (April 2015)
 DOI : http://dx.doi.org/10.17577/IJERTV4IS040228
 Published (First Online): 23042015
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Development of Optimal Route Search Application based on Simulated Annealing Algoritm and Combined Utility Criterion
Valeriy Sirokurov
School of information and engineering Tianjin University of Technology and Education
Tianjin 300222, P.R. China
Abstract Fast development of industry and trade increases importance of optimal routes search. In different cases optimality criterions can essentially differ. Classical traveler salesman problem considers a shortest path as main optimality criterion. Practice shows that when there is need of taking into consideration other factors, route with shortest distance or time is not always optimal. Applying combined criterion for solving travelersalesman problem increases possibility of obtaining optimal solution for users with individual preferences. Method of obtaining combined optimality criterion which considers not only distance and time but also speed limitation on different sections of roads, technical characteristic of automobile vehicle, fuel consumption is suggested in this work. It makes it possible to improve trip planning. Suggested approach is used in combination with simulated annealing algorithm.
On base of this approach was developed software which functionality allows user to specify priorities (simple or combined), specify cities and choose vehicle type. On base of this information and information which is stored in software database, user is provided with information about optimal route, required time, fuel consumption and in recommended speed.
Application scope of developed software includes companies which deliver their own products to users or sales outlets, private use for planning trips.
KeywordsOptimal path, traveller salesman problem, combined optimality criterion, simulated annealing algorythm.

INTRODUCTION
In everyday life we regularly face problems of optimization, without paying attention at it. In industry, commerce, government and other life areas, one frequently needs answers to questions related to operational efficiency. Before such problems usually would be solved using imprecise methods giving results that were both unreliable and costly. Nowadays, they are increasingly being subjected to rigid mathematical analysis, designed to provide methods for finding exact solutions or highly reliable estimates rather than vague approximations.
Combinatorial optimization is a branch of optimization. Its domain is optimization problems where the set of feasible solutions is discrete or can be reduced to discrete one, and the goal is to find the best possible solution or optimal solution (the one that minimizes a given cost function).
The travelersalesman problem can be represented as optimization problem. Its goal is optimal definition of the optimal route which paths through specified cities at least once and implies return to the startcity. Problem statement includes rout utility criterion (shortest path, cheapest path, combined criterion etc.) and corresponding distance matrixes, cost matrixes etc [1,2].
For definition of most profitable rout it is needed to find and describe all possible routes. If it was not done it is not possible to consider solution as most profitable among other existing solutions.
There is a wide variety of methods which can be applied for traveler salesman problem solving. One of the most effective methods is a simulated annealing. Simulated annealing algorithm is a basic algorithmic method for solving global optimization problems. It was borrowed from statistical mechanics and initially it reflected bodys behavior during solidification after applying annealing procedure under the temperature gradually decreased to zero degree [3].
As a rule most of online shops and companies who dont deliver their products directly to consumer use services of delivery companies. Delivery companies have welldeveloped network and they are using software and databases which provide information about goods discharge and loading, about product storage and delivery to consumer or to transportation to another storehouse. Considering that such kind of software is expensive and requires preliminary training from worker who uses it, it may be difficult for common user to work with it.
Those companies which deliver own products should define optimal transportation routes themselves or cooperate with companies which can help to define optimal route. This route can be suitable only for specific situation and cannot be used as pattern for other companies because of technical and juridical reasons.
Considering expenses for services of logistic companies and the fact that after some time there may be need of altering the existing route because it is expedient to develop software which is intuitively understandable for common user and is able to plan roots for transportation and for common trips.
Vast majority of existing software for solving traveler salesman problem gives information about routes length and expected time. Sometimes it is not enough because for some
cases the optimality criterion may be not time but costs. And costs very much depend on fuel consumption which closely related with speed of vehicle. On different parts of road speed limitation defers. Hence, there is need in software which can use combined optimality criterion which considers not only time, length, speed limitation on different sections of the road, but also fuel consumption for chosen type of vehicle.

SIMULATED ANNEALING ALGORITHM AND TRAVELLER SALESMAN PROBLEM
The Travelling salesman problem was first formulated in 1930 and is one of the most intensively studied problems in optimization. It is used as a benchmark for many optimization methods.
Optimization problem statement belongs to problems with NPlevel complicity, as well as most of its special cases. Considering relatively small number of cities (66 and above) it
The solution for TSP on points is a permutation on
points.
If the problem consists of cities , = 1, , , any tour can be represented as permutation of numbers 1 to . (2) is the distance between and . The size of the solute on is
1 !/2.
, = ,
The fitness of each state is the length of path through the cities in that order. The goal is to find a state with the smallest possible fitness.
Given permutation of the cities, and +1 are adjacent cities in the permutation. The permutation has to be found that minimizes (3).
=1
cannot be solved using examination of all options by any of existing computers during time period shorter than several
1 , +1 + , 1
billions of years [4].
Because of this reason simulated annealing algorithm is very popular for solving this kind of problems. Simulated annealing belongs to probabilistic algorithms. Exotic name of this algorithm related to methods of simulation modeling in statistical physics [5], based on MonteCarlo technique.
Research of crystal lattices and atoms behavior during materials controlled cooling resulted in probabilistic algorithms occurrence. Those methods demonstrated very high effectiveness in combinatorial optimization. The method was independently described by Scott Kirkpatrick, C. Daniel Gelatt and Mario P. Vecchi in 1983 [6].
At each step of the algorithm for the current solutions in its neighborhood is selected for a solution , and if the difference in the object function between the new and the current solution does not exceed a given threshold , then the solution eplaces the current . Otherwise, the selected new neighboring solution.
Choose initial state 0 and suppose 0 ,

As long as stop condition is not fulfilled, randomly choose
and if < then +1 = . If >
, than . Suppose + 1.
When 0 , = 0,1,2, – random value with expectation = 0case of local search, when utility value deterioration is allowed. But probability (1) of this change is inversely proportional to deteriorations value, specifically for any .
Where , +1 is distance between two cities (points) and , 1 is the distance between start point and final point. This function is compulsory because traveler salesman problem implies returning to the start point.
For new state generation it positions of two points can be changed but this kind of permutation will not significantly influence the result, method will work slowly and less effectively. The best option is to choose two random cities and invert route between them. It can be generated by 2transform of current solution.

transform:
Select two vertex and at random, > , make the path
, , reverse (4).
1, , 1, , , , +1, ,
1, , 1, , , , +1, ,
Example: some route (1,2,3,4,5,6,7,8), random number generator choose two random cities 2 and 7 after inversion new state is obtained (1,7,6,5,4,3,2,8). After , , reverse the algorithm should calculate and check.
If the difference in the objective function between the new and the current solution does not exceed a given threshold, then the solution replaced the current. Otherwise, the selected new neighboring solution



OBTAINIG UTILITY COFFITIENTS
1, if
P
f j f i,
Depending on users preferences utility criterion can be simple or combined. Simple criterion may be represented by:
ij f i f j
c
exp , if
k
f j f i

minimal time;

minimal distance;
Sequence is important for convergence analysis and should be chosen so that , when . sometimes can be referred to as temperature[7].

minimal fuel consumption.
Combined utility criterion for developed application considers fuel consumption and trip time.

Time minimization.
In case when user looks for route which takes minimal time (5) is used for optimal path definition. Where n is number of routes sections, and I current section, current sections time.
In computation of time speed limitation on different sections of route should be considered as well.
Combined criterion can be found as (10) and (11)
= +
= () +
Utility value for the whole route is a sum of coefficients of different sections of the route. It is obtained using (12), where
=1
=1
i is current section of a route and n is the number of sections.

Distance minimization
=
+
When utility criterion is minimal distance utility function is defined as (6), where current sections distance.
In case when current speed limitation is below then optimal speed for specified vehicle maximal speed limit is accepted as current velocity. When speed limitation is above
=1
the optimal speeds value then optimal value is accepted as a current velocity.

Fuel consumption minimization
Fuel consumption depends on technical characteristics of vehicle and developed velocity. Fuel consumptions and velocitys relation characteristics significantly vary on different velocity rates. This relation cannot be expressed by the same formula for each possible velocity rate. For vast majority of automobiles on speed under 70km/h fuel consumption decreases with speed increment. Speed 8090 km/h can be considered as optimal in relation to fuel consumption minimization. On speed above 90km/h fuel consumption increases with fuel increment. Fig. 1 reflects timespeed curve.
Fig. 1. Timespeed curve
Fuel consumption value is obtained using (7), where is an amount of consumed fuel on current speed. is table value, which is individual for each type of vehicle.
= (() )

Combined criterion
Combined criterion considers two characteristics: velocity and time. (8) is a traditional formula where is distance, time, velocity.
=

reflects relation between fuel consumption and route distance and can be reflected as (9)
= ()


DEVELOPED OPTIMAL ROUTE SEARCH APPLICATION
(ORSA)
The main purpose of ORSA is definition of optimal route between cities considering users individual preferences. ORSA provides a limited access to application database. It is allowed to input data about technical characteristics of automobile, in case when it is not present in database.
Consumer interaction with ORSA can be represented as blackbox model on Fig. 2.
Fig. 2. ORSA blackbox model
Where a, b, c are users input about start city, preferable utility criterion, car type respectively. Utility value depending on users choice can be represented by minimal, minimal distance, fuel consumption or by combined criterion which considers time and fuel consumption. d is a request to applications database for getting or altering data, e is database request output. Database contains information about 25 cities of Ukraine and about 1875 routes between them, names of roads, speed limitation on each section and distances. It also includes technical characteristics about automobiles of Light commercial vehicle class.
Optimal solution (OS) is applications output which is represented by text and graphical output on map. Roads sections are marked by different colors depending in speed limitation (red 120km/h, blue 90km/h, and green 60 km/h). Also user is provided with information about total distance, fuel consumption, and approximate time of trip.
Considering speed limitation on roads the shortest distance path cannot always give a shortest time and minimal fuel consumption. Automobiles of the same brand and class may have different technical characteristics which essentially influence the result of optimal route search.
Simplified scheme of ORA is reflected of Fig. 3. It includes several blocks:

Title block requres use to input following information:

Start city;

Set of cities to visit;

The preferred utility criterion;

Cars (vehicle choice);

Help block. This block allows user to review ORSA manual.

Adding new cars blockcontains allows input of new vehicle and its technical characteristics in case of its absence in database. After that it will be avaliable in Cars block.

Result block risplays an optimal route.
Fig. 3. ORSA model.


EXPERIMENT AND CONCLUSION
In order to check efficiency of applying combined criterion for optimal route search process experiment, described below, was performed.
Estimation of combined criterion usage effectiveness was performed on Ukrainian private breadbaking enterprise. 10 point numerical score was used for this purpose, where 1 is the lowest effectiveness and 10 the highest. According to requirements of enterprise solutions utility should include following factors:

customers satisfaction with delivery quickness;

avoiding products spoiling caused by inefficient route planning;

reasonable delivery expenses elated.
In first part of experiment minimization of delivery time was accepted as utility criterion. In this case relation between fuel expenses and developed speed is neglected. That means that preferable those sections of the route where distance and speed limitation result in time minimization.
On the second step of experiment the combined utility criterion was applied. In regard to fuel consumption for
automobiles used by enterprise for product delivery the optimal speed is 8090 km/h. Velocity beyond this range leads to fuel consumption increase.
Combined utility criterion usage implies development of maximum permissible speed on sections of the route where limitation is lower than optimal speed and development of the optimal speed on sections where this threshold is above the optimal speed.
Effectiveness of routes obtained on base of traditional shortest path criterion was explored in part three of experiment. According to results of first, second and third parts of experiment, efficiency on long distances is 7.7, 9.1, and 6.8 points respectively. Fig. 4 reflects experiment results.
Results of application of combined utility criterion which considers time and relation between fuel consumption and speed closely approximate to the requirements of route efficiency.
Minimization of time is less efficient under normal circumstances and can be more effective only if urgent delivery is required.
Fig. 4. Comparizion of criterions effectiveness
Application of distance minimization is not always financially profitable. There are a lot of route sections on the road which are relatively short but their speed limit leads to time and fuel consumption comparing to longer sections with higher speed limit. Use of this criterion can be expedient for cases of common travel when owner of care is more concerned about minimization of vehicle engine wear.
REFERENCES

David P. Williamson, The Traveling Salesman Problem: An Overview, Cornell University, Ebay Research, pp.56, January 21, 2014

E.L. Lawler (ed.), J.K. Lenstra (ed.), A.H.G. Rinnoy Kan (ed.), D.B. Shmoys (ed.), Wiley, "The traveling salesman problem", 1985.

Metropolis N., Equation of State Calculation by Fast Computing Mashines , Journal of Chem.Phys., vol.2.1, 1953.

Alexander Schrijver, A Course in Combinatorial Optimization, , pp.101 108, February 1, 2006.

Binder K., Monte Carlo methods in statistical physics, Berlin: Springer, 1978.

Kirkpatrick S., Gelatt C. D., Vecchi M. P., Optimization by simulated annealing, Science, vol. 220, pp 671680, 1983.

Aarts E. H. L., Korst J. H. M., Laarhoven van P. J. M., Simulated annealing in Aarts E., LenstraJ.K. (Eds) Local search in combinatorial optimization. Chichester: Wiley, 1997. pp 91120.