Development of Optimal Route Search Application based on Simulated Annealing Algoritm and Combined Utility Criterion

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 traveler-salesman 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.

1. 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 traveler-salesman 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 start-city. 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 on-line shops and companies who dont deliver their products directly to consumer use services of delivery companies. Delivery companies have well-developed 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.

2. 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 NP-level 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 Monte-Carlo 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 ,

   1. 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 2-transform of current solution.

      1. 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

3. 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.

   1. 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.

   2. 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.

   3. 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 80-90 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 time-speed curve.

      Fig. 1. Time-speed 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.

      = (() )

   4. Combined criterion

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

   =

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

      = ()

4. 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 black-box model on Fig. 2.

   Fig. 2. ORSA black-box 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.

5. 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 bread-baking 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 80-90 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

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

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

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

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

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

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

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