SOFTWARE FOR SCHEDULING OF PRODUCTS’ TRANSPORTATION

Глобальные проблемы экономики и финансов: тезисы докладов V Международной научно-практической конференции (Киев-Прага-Вена, 29 апреля 2016)

Section 6: Logistics

YeVhen Matviyishyn

Associate Professor, Doctor of Economics

Professor of the Department of Economic

 Policy and Labor Economics of Lviv

Regional Institute of Public Administration

of the National Academy for Public Administration

under the President of Ukraine,

City of Lviv, Ukraine

SOFTWARE FOR SCHEDULING OF PRODUCTS’ TRANSPORTATION

Thousands of cars, motorcycles, trucks, boats are transporting parcels, bread, milk, containers etc. One engine uses 50-300 ml of fuel every minute. It pollutes air. It is useful for driver to know the shortest route connecting all the points he has to visit in one travel – he pays the minimum for fuel. So if driver has computer and Software for Optimal Route of Traveling (SORT) he can do it.

Problem of choosing the optimal variant of transportation routes is known as Travelling Salesman Problem (TSP). Special web-site is devoted to the applications and current research of this challenge of finding the shortest route visiting each member of a collection of locations [1]. A good source for computational research on the TSP and general optimization is the journal Mathematical Programming Computation [2].  Notable contributions in theory were made by George Dantzig, Delbert Ray Fulkerson and Selmer M. Johnson, who expressed the problem as an integer linear program. They developed the cutting plane method for its solution [3]. The Christofides algorithm is an approach to finding approximate solutions to the TSP. It is an approximation algorithm that guarantees that its solutions will be within a factor of 3/2 of the optimal solution length [4]. As of 2015, this is the best approximation ratio that has been proven for the TSP on general metric spaces, although better approximations are known for some special cases [5]. Collection of locations consists only few points in real situation. So we tried to use method taking into account all possible variants of transportation routes. It is suggested to apply our software SORT created on the basis of algorithm of choosing the best variants of transportation routes. It helps to choose the scheme of transportation with the lowest transportation expenses.

Software SORT is macros for Excel. Macros is created in VBA (Visual Basic for Applications). First of all user must describe the table of durations of travels from each points to others (information on most visited points). He does it first time. Then he will add new information about durations if the new point will arise. SORT finds the optimal route – with shortest total time of traveling through points marked by user. It is useful to mark duration of stay in each point. User marks first point (start) and end point (finish). Start and finish may be the same point (Table 1).

Table 1.

Example of durations of travels from each point to others

Optimal route (solution) looks like Excel-sheet with names of points and durations of travels among them. If user inserts start time (hh:mm) and planned durations of stays in each point SORT will schedule the optimal route (Table 2).

Table 2.

Optimal route (solution)

The great advantage of this software is using of MS Excel (most popular spreadsheet developed by Microsoft for Windows, Mac OS X, and iOS). So it can be used in most of computers, laptops or other gadgets.

Software SORT can be improved. It is possible to take into account type of vehicle. It will be useful to take into consideration influence of weight of goods on duration of travel. It is interesting to insert weather factor as parameter of algorithm in SORT.

Conclusion. Individuals and organizations dealing with goods delivering (farmers, bakers and bakeries, couriers, warehouses, carriers etc.) are direct customers of SORT which helps to find the shortest route visiting each member of a collection of locations. It is useful for driver to know the shortest route connecting all the points – he pays the minimum for fuel.  It is useful for citizens too – an air in their neighborhood will be less polluted by exhausts. Third group of stakeholders consists of consumers – they will receive delivering goods in time.

References:

1. The Traveling Salesman Problem // http://www.math.uwaterloo.ca/tsp/.
2. Mathematical Programming Computation // http://mpc.zib.de/index.html.
3. Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H. G.; Shmoys, D. B. (1985). The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, John Wiley & Sons // https://www.researchgate.net/publication/201976939_The_Traveling_Salesman_Problem_A_Guided_Tour_of_combinatorial_Optimization_Chichester_UK_Wiley.
4. Christofides algorithm: Approximation ratio // http://america.pink/christofides-algorithm_982709.html.
5. Goodrich, Michael T.; Tamassia, Roberto (2015). The Christofides Approximation Algorithm // Algorithm Design and Applications, Wiley, pp. 513–514.