Vehicle Routing Problem Solving System As Acro-GRID Application

Vehicle Routing Problem Solving System as aCRO-GRID Application

Hrvoje Gold, D.Sc, Tonči Carić, D.Sc, Ante Galić, B.Sc, Ivana Ćavar, B.Sc.

Faculty of Transport and Traffic Engineering

University of Zagreb

Vukelićeva 4, Zagreb, HR-10000, Croatia

Phone: +385-1-2380-222 Fax: +385-1-2314-415 Email: {hrvoje.gold | tonci.caric | ante.galic | ivana.cavar}@fpz.hr

Abstract - Transport logistics and fleet management problems often fall into one class of the optimization problems. Finding an optimal set of routes for group of vehicles in the transport network under defined constraints is known as the Vehicle Routing Problem (VRP). VRP represents the NP hard problem. Solving of the VRP problem can be shortened by parallelization of the time critical steps of the sequential algorithm, decomposition of the problem and distribution of its search space among the processors or by concurrent search with different amounts of synchronism and cooperation among sub-problems. The paper presents the description of the developed VRP solving system Venera/Mars and the discussion of results obtained by the implementation of the heuristic algorithms for solving the practical VRP problems in city logistics.

I. INTRODUCTION

One of the main aims of the 'CRO-GRID Applications' project supported by the Ministry of Science, Education and Sport of the Republic of Croatia [1] is to qualify the academic community for the development of distributed applications.

The application of ‘Optimization of Transport Management’ is oriented towards the improvement of organizing the transport of people and goods by solving the practical vehicle routing problems using distributed/parallel implementations of exact and (meta)heuristic algorithms on cluster/grid infrastructure.

The vehicle routing problems represent NP problems and the optimal solution cannot be reached in polynomial time. Therefore, for the correct solution it is appropriate to develop distributed implementations of exact algorithms which can be solved on a computer cluster. In case of solving practical vehicle routing problems that include a number of special additional constraints, the approximate solving methods should be used. The heuristic and meta-heuristic algorithms provide approximate solutions acceptable in practical application. By application of distributed/parallel implementations it is possible to achieve the accelerations of the performance of heuristic and meta-heuristic algorithms.

II. VRP PROBLEM

Determining the optimal route that is used by a group of vehicles in the course of serving a group of customers, represents the vehicle routing problem [2]. Vehicles start from the depot and to reach the customers they operate on the transport network. The solution of the problem is the set of routes. Each route has its first and last stop in a depot of corresponding vehicle. The requests from all the customersshould be fulfilled and all constraints satisfied.

In practice, the basic vehicle routing problem is extended with constraints, for instance, on the allowed capacity of the vehicle, length of route, arrival, departure and service time, time of collection and delivery of goods. The extended classes of VRP are Capacitated VRP (CVRP), Distance Constrained VRP (DVRP), Distance Constrained Capacitated VRP (DCVRP), VRP with Time Windows (VRPTW), Backhauls VRP (VRPB), Pickup and Delivery VRP (VRPPD), and Simultaneous Pickup and Delivery VRP (VRPSPD), Fig. 1. The maingoal in all VRP problems is to obtain the minimal transportation cost.

Fig. 1. Classification of vehicle routing problems

In the case when only one vehicle is serving the customers and there are no additional constraints, the vehicle routing problem is reduced to the travelling salesman problem (TSP). Both problems are NP problems. In the general case the exact solution cannot be found in the polynomial time. For instance, to solve the TSP problem with 10, 15, 18 and 20 customers, a single contemporarycomputer with processing power of 109 operations/sec, needs less than 1 second, 21 seconds, 74 days, 77 years respectively.

To solve the VRP problem the exact, heuristic and meta-heuristic algorithms are in use. The exact algorithms, based on linear programming techniques are limited to solving simple practical problems. In special cases when the set of possible solutions can be reducedthe branch, cut and price, column generation and Lagrange relaxation algorithms are often used.

With heuristic algorithms, e.g. Clark and Wright, Sweep, the acceptable solutions can be achieved relatively fast. The algorithms of improving the heuristic solutions, e.g., 2-opt, try to further optimize an already existing solution by route modifications. The meta-heuristic methods, e.g. simulated annealing, genetic algorithms, tabu search, ant colonies, simulate natural processes and they have proven as very successful optimization methods. In order to solve the practical VRP problems the procedures are used which select the starting routes by construction techniques, and then improve the solutions by linking up of the heuristic and meta-heuristic methods.

The optimized routes have a significant impact on the transport organization by reducing the costs and travelling duration. Practical experiences from literature show that by improving the transport organization by optimizing the routes a reduction of transportation costs of even up to 20% may be achieved. The main users are the carriers who perform the delivery and collection e.g. the transport companies, municipal services, post, courier services.

III. VRP SOLVING ENVIRONMENT

In order to realize the established goal the VRP solving environment that consists of a database with models of test and real-world VRP problems, database of exact and heuristic VRP algorithms as well as VRP solving system has been determined, Fig. 2.

Fig. 2. Vehicle routing problem solving environment

Since each VRP problem is specific and depends on the stated service and transport conditions, the database of test and practical VRP problems assists the user in classification of his problem. The database of exact and meta(heuristic) VRP algorithms is the collection of VRP solvers implemented in sequential or distributed/parallel form. For solving the practical VRP problems the environment is augmented by geographic information system of transport network with traffic attributes.

Distributed/parallel versions of VRP algorithms are executed on cluster/grid network.

IV. VRP SOLVING SYSTEM VENERA

In order to set and visualize the results of the vehicle routing problem, the interactive graphical user interface Venera [3] has been developed, tested, and used for the solution of practical problems. In the current version, Venera has the task of insuring the necessary tools for solving the capacitated vehicle routing problem, solving of the vehicle routing problem with time windows, research, experimenting, and testing of heuristic methods and algorithms.

For the implementation of heuristic algorithms the traffic technologist-oriented programming language Mars was developed and tested on the solving of VRP problems from the literature and from practice. Mars interpreter is integrated in the interactive graphical programming environment Venera. Venera and Mars have been developed in the object programming language Java.

The main window of Venera, Fig. 3, is divided into three parts, one for the table presenting customer data (1), part for table containing data on the vehicle (2), and a part for graphical presentation of the problem (3). Programming window (4) consists of an editor of the source code and a window for displaying system information and messages while the program is running.

Fig. 3. Graphical user interface of VRP solving system

The table with the customer data shows the index, the location by means of x and y coordinates, request for delivery, the earliest time of the start of serving, the latest time of the end of serving and the expected time of serving duration. The table containing data on the vehicles shows the index, colour of the vehicle (route), occupancy, remaining capacity, length of the travelled path and the route recording. Apart from the setting of the problem, the graphical interface allows editing of the customer data and manual design of the vehicle route. If necessary, the form and appearance of display can be adapted by tools supplied inside the interface.

As a means of staying close to the real problems, the possibility is provided of using the traffic matrix of distances between the customers (examples from literature assume Euclidian distances between two points in a two-dimensional space). It is also possible to load problems written in the format of standard Solomon's test of VRP tasks. There is a possibility to test and compare the results obtained by one's own algorithms with the already known solutions and results from the literature.

V. PROGRAMMING LANGUAGE MARS

Apart from the basic numerical and character data types and language constructions, the programming language Mars also contains data types related to the data that are used in setting and solving VRP problems, as well as special statements and functions for local searches and minimization (maximization) of the objective function [4]. In this way the heuristic algorithm programming is significantly simplified and the code is clear and short.

The basic transport data types in the language Mars are CUSTOMER, VEHICLE and ARC. The structure of type CUSTOMER consists of the following data:customer index, customer location coordinates, delivery/collection demand, earliest allowed time of beginning the serving, the latest allowed time of ending the serving, duration of servingand number of visits to the customer. The transport type VEHICLE contains data on the vehicle index, total and remaining vehicle capacity, total travelled path and customer location at which the vehicle is positioned. Thetype ARC consists of: arc length, index of the starting and destination customer and vehicle index which is the arc owner. The values of these variables are usually set before running the program in the very working environment by means of the graphical interface or by loading the concrete VRP problem from the database.

For the needs of the program it is possible to increase the number of transport variables and to declare them subsequently. Thus declared variables represent auxiliary variables, rather than the content of the VRP problem that is being solved. These subsequently declared transport variables are accessed by means of the name stated in the declaration, and their values are assigned to them only during the running of the program. In case one wants to run a block of statements, e.g. within the statementSELECT or FOR loop, one can avoid declaration of the auxiliary variables, since these two programming structures, if necessary, carry out independently the initialization and declaration of the variables. Such approach allows fast interaction between the users and the system as well as obtaining of the answer to simple querieswithout having to declare the variables.

The type of variables CUSTOMER and VEHICLE indicate numerical data which are closely related to the definition of VRP, CVRP, DVRPand VRPTW problems.

The grammar of the language is formalized in EBNF (Enhanced Backus Naur Form) notation. Fig. 4 shows the statement for building of a route between two customers ADDARC and statement to delete the arc DELARC described by syntactic diagrams.

Fig. 4. Syntax of statement ADDARC and DELARC
in language MARS

The basic language constructions, e.g. IF, DO, WHILE, FOR, denote meanings that are similar to those of the majority of programming languages. The statements and functions such as MOVE, ADDARC, DELARC, ADDVEHICLE, DELVEHICLE, DISTANCE, ALLVISITED, SOLVED etc. serve for the communication with the VRP problem objects.

A special place belongs to the declarative statementSELECT which acts as query, and not as an element of the sequential structure of algorithm step description. The form of the querystatement is of similar syntax as the statement of the same name for selection in SQL (Structured Query Language) – a language for making queries to the database management system. The task of the selection statement is to search all the customers, vehicles or arcs that satisfy the stated logical expressions. For all the selected variables, additional search may be requested in order to minimize or maximize the stated objective functions.

Such structure of search conditions is extremely useful in the development and coding of the heuristic algorithms. The statement SELECT automates the search within a part of the neighbourhood which is described in the WHERE part of the statement SELECT. By using the options MINIMISE and MAXIMISE precisely the variable is selected which is contained in the selected part of the neighbourhood, and at the same time provides the desired minimal or maximal result of the objective function. An example of a simple query that will select the nearest customer c to vehicle v is presented in Fig. 5.

Fig. 5. Query structure in language MARS

VI. HEURISTIC VRP ALGORITHMS

Constructive heuristic methods such as the Nearest Neighbour Heuristic (NNH), theNearest Addition Heuristic (NAH), the Sweep method, Sweep-NAH method, the Sweep-Farthest Addition Heuristic (FAH) and the Clark and Wright method, along with the 2OPT or local search e.g. Global Best (GB), First Best (FB) on large neighbourhood generated by  interchange mechanism [5] written in Mars, using standard test data from the literature set and visualized in the Venera, have shown the results close to the optimal results from the literature.

Thus, as an example of the standard test problem E051-05e with 50 customers and 5 vehicles, using the two-phaseSweep-NAH algorithm, the deviation achieved in the Venera environment compared to the best result described in literature amounts to 1.7%, and the result is presented in Fig. 6. The points are customers index and arrows show calculated directions of vehicles for each route displayed on the Venera graphical user interface. To each route is assigned a different colour.

Fig. 6. The solution of standard test example E051-05e

For the example E076-10e with 75 customers and 10 vehicles applying the Clark and Wright algorithm the deviation amounts to 6% compared to the best published solution. The example of the Clark and Wright algorithm realization in Mars is presented in Fig. 7.

'------' ' CLARK AND WRIGHT ALGORITHM '

'------'

CLEAR

AddVehicles CUSTOMERCOUNT, 160

CUSTOMER depot = CUSTOMER(0)

NUMBER end, end0=0

FOR i = 1 TO CUSTOMERCOUNT-1

ADDARC VEHICLE (i-1), depot, CUSTOMER (i)

ADDARC VEHICLE (i-1), CUSTOMER (i), depot

ENDFOR

DO

SELECT ARC arc1, ARC arc2 WHERE

EQUAL CUSTOMER (arc1.TO, depot)

EQUAL CUSTOMER (arc2.FROM, depot)

NOT EQUAL

VEHICLE(arc1.VEHICLE, arc2.VEHICLE)

arc2.VEHICLE.CAPACITY -

arc2.VEHICLE.CAPACITYLEFT <

arc1.VEHICLE.CAPACITYLEFT

MAXIMISE arc1.LENGTH + arc2.LENGTH

DISTANCE(arc1.FROM, arc2.TO)

ENDSELECT

IF FOUND (arc1)

MESSAGE "MAX saving -> " + arc1.FROM.INDEX +

" on " + arc2.TO.INDEX

end = 0

DO

SELECT ARC arc3 WHERE

NOT EQUAL ARC (arc3, arc2)

EQUAL VEHICLE (arc3.VEHICLE,

arc2.VEHICLE)

ENDSELECT

IF FOUND (arc3)

ADDARC arc1.vehicle, arc3.FROM, arc3.TO

DELARC arc3

ELSE

end = -1

ADDARC arc1.VEHICLE, arc1.FROM, arc2.TO

DELARC arc1 DELARC arc2

ENDIF

LOOPIF end = 0

ELSE end0=-2

ENDIF

LOOPIF end0 = 0

DeleteUnusedVehicles

PROCEDURE AddVehicles(NUMBER number, NUMBER

capacity)

DeleteAllVehicles

FOR i=0 TO number-1

ADDVEHICLE capacity

ENDFOR
ENDPROCEDURE

PROCEDURE DeleteUnusedVehicles

FOR i=VEHICLECOUNT-1 TO 0 STEP -1

IF VEHICLE(i).CAPACITY =

VEHICLE(i).CAPACITYLEFT

DELVEHICLE VEHICLE(i)

ENDIF

ENDFOR

ENDPROCEDURE

PROCEDURE DeleteAllVehicles

FOR i=VEHICLECOUNT-1 TO 0 STEP -1

DELVEHICLE VEHICLE(i)

ENDFOR

ENDPROCEDURE

Fig. 7. Clark and Wright algorithm in language Mars

In the first part of the program the FOR structure creates as many routes as there are customers, and each route consists only of the depot and one customer. After the initialization the first SELECT statement selects those routes that need sufficient capacity of one of the vehicles in order to combine the routes and at the same time to maximally save the length of the total travelled distance by the vehicle. The next SELECT statement combines two routes and reduces the number of the necessary vehicles by one. Selection and combining of routes continues until is possible to gain a savings.

VII. TRANSPORT GIS

The solving of the vehicle routing problem is a demanding mathematical problem, but mathematical methods and models alone are not sufficient for its practical solution. It is necessary to combine the VRP model with the real environment of a transport company whose transport organization needs to be improved, e.g. by suggesting changes of transport routes.

As a system for managing spatial data, the Geographic Information System (GIS) appears as one of the obligatory interfaces between the methods developed on the VRP mathematical model, underlying real transport network and the actual working environment of the transport company with all its specific operations. The GIS system, composed of a set of programming tools that are used for the input, storage, manipulation, analysis and presentation of spatial data, links all the spatial data within the applied coordinate system, e.g. geographic latitude and longitude.

In order to input and prepare the real data on the locations of customers as well as to visualize the existing and the resulting routes on a digital map, special GIS application Miranda has been developed. The current transportation layer of the network of urban traffic routes is expanded by a layer of actual constraints acting on the allowed traffic flow, Fig. 8. Also, since by setting the actual VRP problems the addresses of collection or delivery locations are most usually known, rather than their geographical coordinates (latitude/longitude), the address module of the geo-information system has been used. The address module performs the transformation of addresses into adequate digital map coordinates.

For the needs of transforming the actual traffic route network into adequate graph used for the solving of the VRP problem, the layers of the digital map are supplemented by a layer of the shortest paths between the given locations.