13.2. Classical definition of the Vehicle Routing Problem
Definition: the Vehicle Routing Problem deals with the development of circular routes for several vehicles, which shall pass through the provided quantity of target points, provided that all routes shall start and end in one point called depot. Each target point shall have only one route passed. The target of the task is to minimize the total cost of the completion of the routes.
Mathematical definition of the classical VRP:
G (V,E) – the graph with the set of target points (V) and lines (E).
V = {v0, v1, . . . , vn} – the variety of target points, where v0 – is a depot (the target point where all routes start and end).
V' = V \{v0} – the variety of n-target points.
C – the matrix of transportation costs between the targets points, where cij – stands for the cost of transportation between the target points vi and vj.
m – number of vehicles.
Ri = {vi, vj, vk,….} – route of the i-vehicle.
С(Ri) – the cost of route Ri.
The task of routing represents the development of such variety of routes m with minimal total cost, so that every target point from the V-variety shall be visited by one vehicle and only once. All routes shall start and end in the depot. Target function is:  .
14.3. Local peculiarities of VRP
The analysis of the companies dealing with transport logistics and expediting shows that almost all companies can be divided into three groups, provided that the major criteria of such classification is the scope of services provided to the clients:
Large international companies which deal with multimodal transportation services and which are using different transportation means for this purpose (railroad transport, air transport, sea transport, automobile transport and other).
Regional companies which deal with cargo transportation within one macro region / country.
City companies which ensure the collection / delivery of cargo within one city or small district. Internet shops, chains of food and non-food stores and other enterprises can be included into this category.
This article puts an emphasis on the regional and city type of companies because as a rule the multimodal transportations are planned by the experts with due regard to a number of parameters which are based on totally different limitations.
Let’s have a closer look at the operational stages of regional transportation companies:
The first step of the supply chain is the collection of the cargo from the customers and its delivery to the distribution centers; in such centers the goods are distributed in accordance with regions of delivery, after that the vehicle fleet is formed from the vehicles which are currently at company’s disposal.
Then as a rule the goods are delivered to the large transshipment points (warehouses) meant for loading/unloading, here several routs may be combined within one vehicle, due to this action the delivery distance shortens and the costs for VRP’s solution decrease correspondingly.
The third step stands for the delivery of goods from transshipment points to customer’s cities and after that the city companies start their work.
It can be noticed that the transport routing task is solved at every step individually.
Further let’s study the steps of transportation performed by city transportation companies:
The first step is the collection of the cargo from one or several warehouses (plants).
The second step stands for the actual delivery of cargos to the final customer (shops).
Having analyzed the necessities and physical limitations of regional and city transportation companies it’s possible to make the following conclusion – the working methods of the most companies which deal with transport logistics are very similar, that are why it’s possible to develop universal algorithm for the solution of VRP for different companies. The differences between companies lay in the value of specific parameters which influence the speed and calculation quality of the transportation routes and also in some physical limitations and delivery limitations.
Taking to consideration all above mentioned this article reveals the most up-to-date local peculiarities of the task.
15.3.1 Consideration of the vehicle characteristics and characteristics of the cargo to be transported
In the classical definition of the task only homogenous transport is used, so that in order to fulfill the classical task it’s necessary to have the vehicle fleet which consists of the same vehicles.
Each vehicle is characterized by the set of parameters: overall dimensions of the vehicle body and / or overall volume, cargo capacity, list of goods allowed to be transported. The introduction of this peculiarity is connected with physical difference of the transportation means and this peculiarity constitutes an integral part of the task solving. The loading of the vehicle with the cargo which physically cannot be placed on the vehicle due to its weight, dimensions or incompatibility with other cargos has no sense because the solution of VRP will be physically impossible.
It’s necessary to draw the attention to the fact that vehicle can be characterized by operating costs also, within these costs the major part is taken by fuel consumption. Due to that, additional parameter, namely transportation costs for 1 km, was added to the characteristics of the vehicle.
There are two characteristics which are very important for the transported cargo, namely these are weight and volume. Exactly these two parameters are to be introduced to the VRP definition as additional parameters.
16.3.2 Variety of depots and open route
As a rule logistics companies use their own and rented vehicles which can be dispersed across the territory and can be part of different transport fleets. Very often the situation occurs when the owner of the vehicle is the physical person, so that it means absolutely free dislocation of the vehicles. Due to these factors the actual peculiarity of the task definition is the presence of depots variety, herewith the starting point can be comprised of several places most often these are to be warehouses.
Besides, the return of the vehicle without a cargo to the depot appeared to be profitless activity. This factor shall be taken to consideration because it has a crucial importance for the working procedure as it significantly decreases the expenditures of the transportation companies meant for the cargo transportation. Thus, the ability of VRP to build up an open route is in a high demand, because of the departure and arrival points of the vehicle may not coincide.
The definition of the task, taking to consideration this peculiarity, prescribes that the number of depots shall be less or equal to the number of vehicles. So, at the start time each vehicle may be placed at some particular itinerary point or it can represent the autonomous point where loading /unloading procedure does not take place; there is no direct link between the vehicles in the distance matrix. Additional parameter shall be added to each vehicle which should characterize the necessity of vehicle return to the departure point and sometimes it causes the solving of the travelling salesman problem.
17.3.3 The possibility of partial loading / unloading of the vehicle at the itinerary points
This peculiarity covers only the clients who are dealing with transportation of consolidated cargos, it means that the carrier can either collect the cargo and transport it to the warehouse or collect the cargo from the warehouse or from the other clients during the execution of its itinerary route. For example, big chain stores can redistribute the goods between the selling points depending on the demand during particular time period. Regional companies may use this peculiarity to redistribute the cargos between vehicles at itinerary points - warehouses meant for cargo batching.
In order to be able to use this supplement to the definition of VRP definition each itinerary point shall have two sets of characteristics, these are cargos to be dispatched from the point and the goods to be collected.
It should be mentioned that in case of such VRP definition the necessity of cargo redistribution appears, because the necessity of itinerary points can be satisfied by several means, this is connected with the fact that the goods which are required at the point may be located in different places.
18.3.4 Transportation of cargo which consists of various goods
In the classical definition of the task only one type of goods is used for transportation needs, very often it does not confirm with the reality, because the cargo to be transported can be quite different. It is stipulated that most often the transportation of grouped cargos takes place, which means that one cargo includes goods from different manufacturers which were collected in the united distribution centers.
Due to that fact such goods characteristics as designation (code), weight, volume and type of goods are used in the definition of the task.
19.3.5 Consideration of the service priority of the point
As in this task definition we consider non-homogenous goods and limited number of vehicles, in terms of service provision for the points, it's necessary to take to account the priority of these points’ visiting during particular time period. This is stipulated by the limited durability of goods, time prescribed by the execution of order and other factors. As the number of vehicles is limited, sometimes it's not possible to visit all itinerary points within particular period of time. The service prioritization can be applied as a solution of this problem.
This article does not concentrate on the semantics of the concept “priority”. For food commodities “priority” may mean the propinquity of the selling due date of the goods (0 –the goods are in the warehouse, 1- the goods are to be written-off), for industrial commodities, for example, “priority” may stand for seasonal necessity to change the goods. The determination of the priority concept can be widened in order to meet the needs of each enterprise individually.
It means that at every itinerary point each cargo has its own service priority in terms of acceptance / consignation.
The introduction of service priority allows decreasing the total costs of cargo transportation. Such target may be achieved due to addition of the cargos with lower priority to the vehicles which are not loaded to the full, therefore the price of 1 km transportation will increase insignificantly, but the effect of economical growth appeared to be quite sufficient.
20.3.6 Interconnection with transport task
Taking to account everything above said, it shall be mentioned that such definition of the task represents the combination of two tasks: the transport task in its classical definition and transport routing task. The first task focuses on the distribution of the goods between the points, the second task deals with development of the optimal routes for particular vehicles. Let’s have a closer look at the classical task definition:
Definition: transport task – to develop optimal transportation plan of a homogenous goods from homogenous points of departure to homogenous points of destination.
Mathematical definition of classical transport task:
A1,A2,…,Am – points of departure,
B1,B2,….Bn – points of destination,
С – price matrix, where сij is the cost of transportation of the cargo unit from i-point of departure to j-point of destination,
ai – stock of goods in the i-point of departure,
bj – demand for goods in the j-point of destination,
X – transportation matrix , where xij stands for number of cargo units which are to be delivered from i-point of departure to j-point of destination,
The target: it’s necessary to meet the customers’ demand with the warehouse stock under condition of minimizing of transportation costs. Target function:  .
Let’s have a look at the complex transport task. The first stage of task solution shall be the creation of consigners’ orders which will define the list of goods to be delivered, points of departure and points of destination, date of departure and delivery of the goods. The second stage stipulates the development of routes which will include parts of orders in case it’s not possible to locate the full order within one vehicle or several full orders, if these are small orders which can be placed together on one vehicle. During the execution of the itinerary route the vehicle can whether unload the cargo at the itinerary points or load it.
The separation of these tasks limits its application, so for the purpose of finding solution for the wider spectrum of cargo transportation tasks it appears to be reasonable to consider these tasks as a complex. It should be taken to consideration that with the help of complex transportation task it’s possible to decrease the transportation costs significantly, because sometimes the solution found for the task will be economically efficient.
It shall be mentioned that the definition of the task described in this article stipulates the consideration of several kinds of transport tasks.
If the limitation for itinerary routes is eliminated, the task transforms into the transport task where each itinerary point can act whether as a consigner or as a consignee.
If the limitation for the homogeneity of goods is eliminated, the task transforms into multi product transportation task where every itinerary point can whether contain or demand several different goods.
Due to above mentioned facts we face the necessity to describe the transport task which includes the routing task and which uses the variety of local peculiarities of two tasks in order to draw the task denomination closer to real life.
|
