Vehicle Routing Problem

Размещено на http://www.allbest.ru/

1. Introduction

architecture route construction customer

Vehicle Routing Problem (VRP) is NP-hard combinatorial optimization problem. In simple words, it can be explained as follows. We have a set of points or vertices, which represent shops or customers with some demands. In order to serve all demands, there is a number of vehicles with some characteristics. The problem has various constraints, such as, vehicles may have limited capacity (Capacited VRP or CVRP), they should start their routes from determined points, one or many, different vehicles may have different properties; customers may have time windows, constraints on type of vehicle, their demand includes different types of cargo etc. All these constraints are required for real-life problems. The goal of VRP is to minimize the cost of the solution, where costs consist from fixed vehicle cost and travel costs between customers.

VRP is famous and popular problem in logistics and transportation, that's why it is considered in many real-life applications. Dantzig and Ramser initially introduced the problem in 1959 as they proposed the first mathematical programming formulation for the problem [1]. First greedy heuristic was presented by Clarke and Wright in 1964 [1] and since that time many different models, algorithms, and approaches were proposed for various VRP forms.

The variety of VRPs can be explained by the fact that it occurs in many real-life situations. Those situations impose additional constraints, which generally only make the problem more sofisticated. For example, we may consider truck-and-trailer routing problem instead of VRP. In this case, every vehicle is represented by truck and trailer and, as a result, we have some new possibilities. For example, some customers can not be served by vehicle with trailer. Such problems are called TTRP (Truck-and-Trailer Routing Problem) in literature and there were suggested a lot of heuristics last years for these type of VRP [2][3][4].

Next, the set of vehicle may be heterogeneous (Heterogeneous Fleet TTRP or HFTTRP). It means that every vehicle has various capacities, travel and fixed costs. Additionally, there may be constraints for vehicles, such as every customer have only a subset of vehicles that may serve this customer. In this case, it is Site Dependent TTRP (SDTTRP) and for this problem there were developed heuristics as well. For example, Semet and Taillard (1993, [5]) developed a tabu-search for SDTTRP with Time Windows (SDTTRPTW).

The problem considered in this work is even more elaborate. Additionally to SDTTRPTW (Drexl, 2011 [6]), soft time windows and split-deliveries are added to the model. The model, heuristic and algorithmic approach were presented in Batsyn and Ponomarenko (2014, [4]). In this work, local search and tabu local search are proposed as options to improve the cost of solutions obtained after greedy heuristic. The goal of this work is to create and program algorithm, which implements heuristic with elements of tabu search for SDTTRPTW with soft time windows and split-deliveries and, at the same time, its solutions are satisfactory in cost or even better than solutions obtained from old architecture greedy algorithm. More about old and new architecture is described in chapter 3.

The problem may be divided in a number of tasks:

- Develop new architecture for route construction, which allows philosophy of insertion and, more importantly, deletion of customer in route. Additionaly, it is desirable for this architecture to be easily extensible, it should allow to find errors in a simple way.

- Create and program algorithm of local search and tabu search with possibility to go through infeasible solutions in order to be able to leave local minimums and visit vast neighborhoods.

- Research and develop the structure of heuristic in such way, so the algorithm find satisfactory solution in acceptable time period.



2. Description of a Model

2.1 Description

In this work, SDTTRPTW with soft time windows and split-deliveries is considered. First, we have truck-and-trailer constraint. It means, that every vehicle has truck and many of them has additional place to have cargo - trailer. Its presence increases total capacity of a truck, but at the same time, travel costs also increase; moreover, some customers cannot be served by trucks with trailers, they must be served only by trucks as vehicles. In real life, it means that this customer or shop has little space for parking or it is impossible to get to the customer as a road train because streets are too narrow. As a result, to serve these customers, we must use truck without a trailer or we should find a place to leave the trailer before visiting such customers. As such place vehicle can use another customer, then, it is possible that this customer unloads his cargo from the trailer while the truck goes on a truck subtour to serve other, truck customers. Another option is to leave the trailer in some special transshipment location, close to truck customer (or truck customers) where it will stay while the truck visits truck subtour. Finally, we can have situation, when total demand of truck customers is more than the capacity of truck part of vehicle or vice versa, trailer customers have total demand more, than can be placed in trailer. In this case, it is possible to make a reload - in a place, where we leave trailer, we may spend time to transfer goods from trailer to truck or backwards.

Next, Site Dependent constraints mean that every vehicle has different capacities, travel and fixed costs. Additionally, for the problem in this work, we have two types of goods - one that needs refrigerator and one that do not. In other words, first type is some fast-spoiling products, and if a customer has a demand of such products, only a vehicle with refrigerator must serve it. Besides, some trucks may be too big to serve some customers because of listed above reasons: narrow roads, small parking place, and etc. These constraints create the variety of possibilities, to choose ideal vehicle from feasible set of vehicles. Basically, solver of Site-Dependent VRP should take into account that some vehicles should be used only for a small group of customers, otherwise this group will stay unserved and the solution will be infeasible because of that.

Another important feature of the model is time windows. In the model, there are two types of windows - hard time windows and soft time windows. Hard time windows describe the time when the customer may take in vehicles for unloading and other operations (to leave trailer, to take trailer, to reload). In other words, it is time when the customer or shop works, so it has working personnel at the time. All the operations, which involves personnel of the customer, must be done within the hard time window. Usually, hard window is the time from morning till evening. If the vehicle is late for hard time windows, it has to wait next day and next hard time windows for unloading or other operations. Basically, it makes the route infeasible. Another type of time constraint is soft time window. It is a small period of time (2-3 hours, sometimes less or more), which is situated somewhere inside of hard time window. Soft time window is a preferred time period for unloading the goods. In other words, every shop has a desirable time when it would be the most ideal to take in vehicle. The delivery is inside soft time window if unload of the cargo starts between start and end time of the soft time window. If the delivery on time is not possible because of previous deliveries in route or the construction of the route, the vehicle arrives to the customer earlier or later than soft time window, and it has to be unloaded outside the soft time window, it is called a violation of soft time window, in other words, delay. However, if the vehicle arrived earlier, it can wait until soft time window to start unloading, and in this case, it is not a violation. In the whole solution there can be only limited number of delays with respect to the number of customers.

Finally, there is additional possibility to change routes - it is a split-delivery. In a split-delivery, a customer may be served by two or more vehicles, every one of which has a part of goods for this customer. It is necessary, if the customer has a demand bigger than the capacity of the biggest vehicle. However, even for customers with small demand it may be useful and split-delivery may help to reduce costs. For example, one vehicle in split-delivery may deliver the part of demand, which does not have to use refrigerator (these vehicles usually cost less). However, this situation adds some complexity. For example, split-delivery does not violate the soft time window if the biggest part of split delivery unloads in soft time window. Also, as with the number of delays, the model has a constraint on a number of split-deliveries. Finally, customers prefer to unload one delivery at one time.

2.2 Mathematical Programming formulation

First of all, we have to determine objective function. Let's denote:

total number of stores, number of trailer-stores (stores that can be served by truck with trailer), number of truck-stores (stores that can not be served by truck with trailer) and number of transshipment locations (places to leave trailer without unload). 0 is the index for depot, indices from 1 to are assigned to trailer stores, indices from to are assigned to truck stores, and indices from to are assigned to transshipment locations. We define:

The set of vehicles is marked as , where is the set of vehicles with trailers, is the set of vehicles without trailers and is the set of vehicles with refrigerators. is fixed cost of vehicle We also need some variables:

Objective function looks like:

We minimize the sum of all travelling costs and fixed costs in the objective function. Next, we denote that are capacities of vehicle, its trailer and its truck correspondingly, and are total demand of customer , and demand that needs refrigerator. Also, we have , it is a fraction of demand of customer , which is delivered by vehicle , and , where it is equal to 1 if some fraction of demand for customer is served by vehicle . Now, we can describe demand and capacity constraints as:

It is easy to see that these constraints describe that all demand should be satisfied, and we should not exceed the capacity of vehicles. Additionally, we can describe travelling and flow conservation constraints:

These constraints show that we can not visit truck-stores using vehicles with trailers, if vehicle serves customers, it should travel through them and if we visited customer, we should travel arcs to and from this customer.

For hard and soft time windows constraints we need additional variables and denotations. Let be the arrive time, begin time of the delivery and end time of the delivery of vehicle to customer ; are open time, close time, start of soft time window and end of soft time window for customer . is the service time of total demand of customer for vehicle , is the total time to leave trailer and make load transfer at place for vehicle , is the time for vehicle to travel from to with () or without () trailer. Variable is equal to 1 when vehicle leaves trailer at place . is a huge positive number.

______________________________________________________

____________________________________________________

____________________________________________________

____________________________________________________

All those constraints restrict us to violate hard time windows. For example, last constraint tells that if we leave trailer at place and travel from to without trailer and with this vehicle, begin time of delivery for customer should be later than arrive time to place , plus time to leave trailer at place , plus time to travel the arc .

For soft time windows constraints we should include another variable: is equal to 1 when vehicle does not deliver to customer or make this delivery out of soft time window. is equal to 1 when soft time window is violated for customer ; is a limit on a number of soft time windows violations.

First constraint describes soft time windows, second constraints checks every customer for soft time window violation, and third constraint establishes the limit.

For split-deliveries constraints we need variable , which equals to 1 if a customer is split, despite that it is possible to place all demand in one vehicle. Parameter limits the number of split-deliveries.

Those constraints limit the number of split-deliveries in solution. However, we need to restrict the situation when two vehicles unload at the same time at the same customer in case of split-deliveries. For this case, we have variable , which equals to 1 when vehicle starts delivery to the customer later than ends its delivery to the same customer.

First and second constraints require that if vehicle starts delivery to the customer later than ends its delivery. If , last constraint ensures that vehicle starts delivery to the customer later than ends its delivery.

Last constraints are truck subtour capacity and refrigerator constraints:

is total demand, served by vehicle in truck subtour up to customer . Constraints ensure that total demand in truck subtour is less than truck capacity. Last constraint emphasizes that demand, which needs refrigerator, should be served by vehicle with refrigerator.

2.3 Basic algorithms

2.3.1 Greedy Algorithm

For our purposes of creating heuristic with elements of tabu search, we need to have some way to construct initial solutions. Greedy algorithm is used to construct first solutions, which are feasible.

The basic idea of the algorithm is a sequential building of routes, where each route is completed by adding customers using greedy rule. The process of building the solution is completed after there are no unserved customers.

At the start of algorithm, every customer is unserved. Every route is constructed as follows. The algorithm sorts unserved customers by the travel cost from depot to the customer, then, it chooses the customer with one of the biggest travel cost - this customer is initial customer for the route. If the initial customer cannot be served inside of soft time window, so it can be served only after the end of soft time window, we consider the delay of this customer as forced or mandatory delay. After that, the algorithm finds the most suitable vehicle for this customer. Now, the route constructed with this vehicle and the initial customer. Next, the algorithm determines the number of allowed delays for this route and tries to insert every still unserved customer in this route in every possible place to determine the insertion, which increases the cost of the solution the least and conform to the number of allowed delays. At the end, after we looked through all unserved customers, the best insertion is implemented. The algorithm repeats this process until there are no possible insertions or, in other words, every insertion creates infeasible route. Route construction repeats itself until there are no unserved customers left.

When the algorithm tries to insert a customer into existing route, it tries to insert the customer in every possible position between any two sequent existing points. The algorithm checks possible variants such as adding new place to leave trailer without unload or changing the place to leave trailer. If the customer has more demand than free capacity of vehicle, there is a probability to permit a split-delivery for the customer.

Basically, greedy algorithm needs only operations of insertion and estimation of cost.

2.3.2 Tabu search heuristic

The idea of tabu search is derived from local search heuristic. In local search, we have initial solution, which is improved gradually. Each improvement is a slight change in a solution, which improves its cost or another measure. So, the local search has a neighborhood - it is a set of all possible solutions, which we can obtain from current state of solution by doing slight changes to different parts of solutions.

In case of SDTTRPTW, every solution is a set of routes and every route is a sequence of served customers, which starts and end at the depot. Then, every solution has cost which is the sum of costs for every route in solution. So, the local search algorithm tries to improve that cost. We may say that slight changes in solution are changes in routes, where we take a customer from one route and insert it in another route. Further in text, such changes will be called moves.

Let's look at the procedure of deletion in more details. The procedure should consider all possible variants of customers disposition. Let's denote:



- is the store, visited by vehicle with trailer

- is the store, visited by vehicle without trailer

- is the store, where vehicle leaves trailer for unloading

- is the transshipment location

- is the point, where vehicle returns to the place where it left trailer to take it and continue the route.

- is anything of listed above.

All possible variants of customers deletion from the route can be consolidated as 3 basic cases:

1) Simple deletion. Here we need to take the customer from the route. It is simple, because it is enough to calculate new distance and cost to the next customer and shift all subsequent customers earlier in time (if triangle inequality is true):

On the picture two options are presented, route with trailer or without. In second case (truck subtour) we also have to find the place where we left trailer and understand whether we need to change load transfer time for the trailer. Change to cost function is: .

It is worth noting that after this deletion the route might become empty. In this case for vehicle , which serves this route.

In this simple case, we do not need to create any new points in the route.

2) Truck subtour deletion. Here we choose to delete such customer, that after deletion we no longer need the truck subtour.

The first case, when the place for trailer is transshipment location and there is only one customer in the truck subtour. After we delete this customer we do not need to visit transshipment location as well, therefore we can travel straight to point . And, for the objective function, . In the second case, place where we leave trailer is another store, and truck subtour includes one customer. After we delete this customer, we no longer need to leave trailer at place and return to it, we can just visit this place as trailer-store. Objective function changes as .



3) New leave place for trailer in truck subtour:

In this case, we delete the first customer in truck subtour or the customer, where we leave trailer for unload. As the result, we have to find a new place for truck subtour to leave trailer. On the picture, new place to leave trailer is determined by the customer . If this customer can be served by vehicle with trailer, we leave the trailer for unload at this customer, otherwise, we find the closest transshipment location for customer . As the result, if truck subtour started with transshipment location, otherwise ; if can be served by vehicle with trailer , otherwise ; if we assume that last customer in truck subtour is , total .

At the end of step, if one of such moves improves the cost of solution, the algorithm will execute it and gets a new current solution. After that the local search is performed on the current solution.

However, local search has one big problem. This algorithm gets stuck at local minimums. It means that after it performs some steps of local search the algorithm finds solution, which cannot be improved in cost. And here is the main idea of tabu search - to expand the neighborhood of local search by allowing “prohibited” moves - such moves that increase cost of solution or make the solution infeasible. For our case of SDTTRPTW, the solution may be infeasible if we violate delay or split-delivery constraints, if we allow creating over-capacitated routes or violating hard windows.

Usually in tabu search algorithms there are some memory of recently executed moves - the algorithm needs this memory in order to remember what moves it should not perform for a while. For example, let's consider the case, where we cannot improve the cost of the solution, so we make a “bad” move, which increases this cost by delta. After that, there is a high chance that we make this move back because it will decrease cost of the solution. The algorithm will not perform this move only in two cases: firstly, if after “bad” move there is a possibility for a better in cost move (it decreases cost more than by delta), or secondly, we prohibit to perform this move back.

So, to conclude, for tabu search there is a necessity to develop deletion algorithm and some ways to expand the neighborhood of local search. Also, we should not forget about procedures, which make feasible solution from infeasible.



3. Structure of the program

3.1 Old architecture and motivation for refactoring

As it was said in introduction, the goal of this work is to create a heuristic algorithm with tabu search elements. First implementation of such algorithm was created on an old programming architecture, which implemented greedy algorithm for SDTTRPTW with soft time windows and split deliveries problem. The main point of the old architecture is speed of program - it was built in C++ language.

In old architecture every customer is presented as one object. Route contains the sequence of served customers, every served customer is a shell for customer. Every customer has to know when it is served and how long the delivery is taking, so object Customer contains fields for arrive time of vehicle, total service time, leave time, several types of wait times, delay times etc. All these fields are duplicated two times - one for “true” values and one for “temporary” values. Also, third duplication of those fields is in pointers. When the greedy algorithm tries different customers to insert in some route, it switches pointers to “temporary” fields, so the algorithm works using those fields. When the greedy algorithm found the best possible customer for insertion, it switches fields of this customer to “true” values and fills them with true values. Because there is no operation of copying values or objects, the program works fast. So, the program can go through a hundreds solutions in seconds.

However, this approach works poorly together with local search. First of all, for split delivery cases, true values in customer match only last delivery to the customer, so to work properly with routes, every route needs to be rebuilt from the start. Secondly, old architecture is tuned for insertion operations with time shifts. When deletion procedures were applied, the architecture showed unstable behavior, shifts worked with mistakes, and the work of program was unstable. Moreover, the old architecture is absolutely unsuitable for any neighborhood extension, which creates infeasible solution, basically modifying the old architecture to be used in unfeasible neighborhood would be as hard as creating new program.

Greedy route construction algorithm old architecture

firstCustomer = findDistantCustomer()

vehicle = findProperVehicle(firstCustomer)

route = constructRoute(vehicle,firstCustomer)

while(true)

switchToTemporaryParameters()

bestCost = Infinity

bestCustomer = null

for every customer in customersList

cost = insertCustomerInRoute(customer,route)

if cost < bestCost

bestCost = cost

bestCustomer = customer

if bestCustomer != null

switchToTrueParameters()

route = insertCustomerInRoute(customer,route)

else

end GreedyRouteConstructionAlgorithm

That's why it was decided to refactor the program or, generally, create new architecture for the heuristic algorithm. The new architecture should meet several requirements:

- Operation of insertion and deletion should be considered equal in complexity and use the same or similar interface. Basically, it means that both operations should influence the route in the same way and all the accompanying procedures should be the same or work the same way.

- The architecture should be extendable to match changing constraints or order of operation. Real-life problems often change their constraints under the influence of changed policy or new conditions.

- The architecture should not be prone to mistakes, the code should be more clear and apprehensible.

3.2 New architecture

3.2.1 Base thoughts

The programming language for the new architecture is Java. The choice is caused by some reasons:

- Strong object-oriented direction of the language. SDTTRPTW consists of different concepts, which can be reflected in classes.

- Automatic memory management. The task of programmer in big project is much easier if he has no concern about correct use of memory.

- Java is cross-platform language, which allow to execute the program in different operation systems, Windows and UNIX-type.

The next thought in the architecture is that tabu search needs initial solution. However, it needs only one initial solution to start its work. That is why we do not need speed-tuned greedy algorithm. Basically, the program may work some seconds on obtaining one greedy solution, which may be worse than solution, which would be obtained from old architecture program. However, this solution will be significantly improved by heuristic.

The baseline is - the program can copy objects in all situations. For example, in order to try to insert a customer in some route, the program will create copies of route and customer and will insert customer copy in route copy. After that, the program will estimate the cost of this route if it is feasible. If the cost is better the previous options - the route will be remembered, otherwise - it will be discarded. Java garbage collector will destroy this object without programmer concern.

3.2.2 Core concepts

In the new architecture every route contains two different representations of itself, tied one to another.

Actions. First representation of the route is the sequence of actions. Every action is a simple construct, which represents atomic event in route. For example, every travel between two customers is atomic event. The goal of this representation is to make every atomic event as simple as possible and to have an opportunity to use one interface to work with any action. Every actions has two time marks - the start and the end of action, the customer, which is “responsible” for this action and link to global information. The list of actions is as follows:

Travel: the event of moving from one point to another.

Wait: the event of waiting at the customer, where nothing happens.

Park/Unpark: events of parking and unparking a vehicle.

Unload: the event of unloading the cargo

Couple/Decouple: events of leaving or taking a trailer

The “responsible” customer is a customer at which the event is taking place. However, for Travel action there is no such customer. In this case, responsible customer is the one, that vehicle leaves. Wait Action is a special type of Action, which is used when the program needs to stay for some time at the customer in order to start unload operation inside of soft time window. Sometimes, Wait Action is somehow fictional Actions, because it starts and ends at the same time, so there is no wait time at all. However, Wait action is used in every Route Point (described below) for purposes of uniformity, or, in other words, to work with all Route Points through the same interface and with the same interactions as it was described in suggestions to the new program architecture.

All the actions have common interface to work with. The main operations of actions are creating an object and shifts. Every action may be shifted in time by some delta. However, actions differ in their reactions on shifts. For example, Travel, Park and Unpark actions just change their start and end times by delta. Unload, Couple and Decouple actions change their start and end values by delta and check if their time period settles inside hard time window for “responsible” customer.

The rules for Wait action are a bit harder. Basically, if Wait action is shifted right, only start time point is changed by time delta. Then, the program checks some conditions:

- if after the change, end time is less than start time, end time becomes equal start time.

- if after the change end time is still more than start time, end time decreases (it can not increase) to one of the possible values:

o if start time of Wait is closer to end time than start of soft or hard window, then end time becomes equal to start time.

o if start of soft time window is closer to end time than start time, then end time equals start of the soft time window

o if start of hard time window is closer to end time than start time, and end time is already less than the start of soft time window, then end time is equal to start of hard time window

Similar rules are applied for left shift.

Shift Right Procedure for Travel, Park and Unpark Actions

shiftRight(delta)

start = start + delta

end = end + delta

Shift Right Procedure for Unload, Couple and Decouple Actions

shiftRight(delta)

start = start + delta

end = end + delta

if(periodNotInHardTimeWindowOfCustomer(customer, start, end))

Shift Right Procedure for Wait Action

shiftRight(delta)

start = start + delta

if(end < start)

end = start

if(end > start && end > startOfSoftTimeWindow(customer))

end = max(start, startOfSoftTimeWindow(customer))

if(end > start && end < startOfSoftTimeWindow(customer) && end > startOfHardTimeWindow(customer))

end = max(start, startOfHardTimeWindow(customer))

Additionaly, Wait Action has two special shifts - soft and hard shift. Soft shifts only change start or end time, hard shifts change both to one value. This structure for Wait actions helps with route optimization and compression.

Sequence of actions forms a representation of route, which consists of atomic events. Usually, this sequence looks as follows:

Travel - Wait - Park - Unload - Unpark - Travel - Wait - Park - Unload - Unpark - … - Unpark - Travel.

Route Points. Route Points are the second representation of route. Every Route Point is a point, visited by vehicle in route. Route Point consists of the number of actions, which are different for various Route Point types. Every Route Point contains total delivery for this Route Point.

Depot Point. This Route Point represents Depot points. Every route contains two such Route Points - at the start and at the end of Route Point Sequence. Start Depot Point do not contain Actions, end Depot Point has one Travel action.

Unload Point. Basic Route Point for almost every case, when Unload Action happens. It consists from sequence of actions: Travel - Wait - Park - Unload - Unpark. Unload Point may represent a point of unload with trailer, and a point of unload without trailer, or a point that is inside of truck route.

Leave Trailer Without Unload Point. This Route Point means that at this customer, vehicle leaves trailer and goes on a subtour. It consists from sequence of following actions: Travel - Wait - Park - Decouple - Unpark. In many cases, if customer should be served by truck without trailer, the program creates connected Route Points - Leave Trailer Without Unload Point, Unload Point, Take Trailer Point.

Leave Trailer With Unload Point. This Route Point is similar to Leave Trailer Without Unload Point, however, in this case, the customer, where trailer is left, unloads cargo from the trailer. The sequence of actions is: Travel - Wait - Park - Decouple - Unpark - Unload. Unload action in Leave Trailer With Unload Point is only action, which is not consistent with surrounding actions. Usually, in actions sequence, for two consequent actions, the end time of the previous is the start time of the next action; however, for this Unload it is not true.

Take Trailer Point. This Route Point is connected to Leave Trailer Without Unload and Leave Trailer With Unload Point (Leave Trailer Points). For every Leave Trailer Point in sequence of Route Points there is Take Trailer Point later in the sequence. The part of sequence between Leave Trailer Point and Take Trailer Point is called truck subtour and inside of that part of sequence there can occur only Unload Points. Leave Trailer Point and corresponding Take Trailer Point have the same “responsible” customer. The action sequences is: Travel - Park - Wait - Couple - Unpark. It differs from other Route Points, because Wait action happens after Park. Wait time is used here for Leave Trailer With Unload Point and this period of time is not zero if vehicle returns to Take Trailer Point before Unload action in Leave Trailer With Unload Point ended.

As with the Actions, all Route Points have a common interface to work with. Main functions of this interface are also shifts. There are code examples for three types of shifts for Unload Point:

int shiftPoint(int start) throws ActionConstructionException

{

travel.shiftRight(start - travel.startAt());

wait.shiftRight(travel.finishAt() - wait.startAt());

park.shiftRight(wait.finishAt() - park.startAt());

unload.shiftRight(park.finishAt() - unload.startAt());

unpark.shiftRight(unload.finishAt() - unpark.startAt());

return unpark.finishAt();

}

int shiftLeft(int start) throws ActionConstructionException

{

travel.shiftLeft(travel.startAt() - start);

wait.shiftHard(-(wait.startAt() - travel.finishAt()));

park.shiftLeft(park.startAt() - wait.finishAt());

unload.shiftLeft(unload.startAt() - park.finishAt());

unpark.shiftLeft(unpark.startAt() - unload.finishAt());

return unpark.finishAt();

}

int shiftRight(int finish) throws ActionConstructionException

{

unpark.shiftRight(finish - unpark.finishAt());

unload.shiftRight(unpark.startAt() - unload.finishAt());

park.shiftRight(unload.startAt() - park.finishAt());

wait.shiftHard(park.startAt() - wait.startAt());

travel.shiftRight(wait.startAt() - travel.finishAt());

return travel.startAt();

}

Shift Point function performs shift of whole Route Point so it starts at the time start; Shift Left function shifts whole Route Point so it starts at the time start and Wait time period is equal to zero; Shift Right function shifts whole Route Point so it ends at the time finish and Wait time period is equal to zero.

To summarize, Actions create sequence of atomic events in route, and this representation helps simplification and visualization purposes, also it is comfortable to finalize Route times through Actions, because they generally go one after another. With Actions, one can clearly see the construction of the route, how it goes on, which helps in finding mistakes and final visualization of result. Route Points represent in some way a shell for actions, because some of the atomic operations a different for the same actions in different Route Points. Also, Route Points are obvious entities for Vehicle Route Problem, because every Route Point is basically a point that vehicle visits.

3.3 Algorithms implementations

3.3.1 Insertions and Greedy Algorithm

Actions and Route Point representations work together as following. When the program performs an insertion of some customer at some place in route, first of all, the program creates a set of actions that are required for this special case and inserts them in the appropriate place in the sequence of actions. After that, program create Route Point or Route Points according to the special case that the program is in. Next step is connection between Actions and Route Points representations - every Route Point sets its actions in accordance with the position of the Route Point in the sequence. After that, the program finalizes times - it means that whole sequence of actions is checked to be correct according to timetable rules, in other words, every action starts when the previous action ends. If some of the actions do not happen inside hard time window, this new route is recognized as infeasible and is discarded.

Code example for insertion of a simple Unload Point:

int insertUnloadPoint(int startTime, Customer customer, ListIterator<Action> iter, Customer nextCustomer, int unloadTime, boolean hardWindow) throws VRPException

{

int timeToStartParking = determineParkingTime (customer, startTime, hardWindow);

if (timeToStartParking == - config.BIG_NUMBER)

throw new RouteConstructionException();

Wait wait = null;

if (timeToStartParking != startTime)

{

wait = new Wait(customer, startTime, timeToStartParking - startTime, vrp);

}

else

{

wait = new Wait(customer, startTime, 0, vrp);

}

Park park = new Park (customer,wait.finishAt(),vehicle.getParkingTime(),vrp);

Unload unload = new Unload (customer, park.finishAt(), unloadTime, vrp);

Unpark unpark = new Unpark (customer, unload.finishAt(), vehicle.getParkingTime(), vrp);

Travel travel = new Travel (customer,unpark.finishAt(),nextCustomer,vrp);

iter.add(wait);

iter.add(park);

iter.add(unload);

iter.add(unpark);

iter.add(travel);

customer.increaseNumberOfDeliveries();

return travel.finishAt();

}

There are possible a number of different cases for insertion a new Route Point. However, in comparison to old program architecture, in new program, the number of cases was reduced for simplification purposes. All insertion cases are divided in three subcases:

1) First customer insertion. When the route is empty and the first customer is inserted, there are two possible options. If the customer can be served by the chosen vehicle with truck and trailer, there is an insertion of Unload Point. If the customer can be served by this vehicle but without trailer, then the vehicle is considered as vehicle without trailer hereinafter for this whole route; there is an insertion of Unload Point as well.

2) Truck Point insertion. If the place to insert new customer is inside truck subtour, then the program performs Unload Point insertion, however, it checks if total cargo of all customer in the subtour and cargo of new customer can fit in the truck, otherwise the route after this insertion is infeasible.

3) Trailer Point insertion. In this case, the program wants to insert the customer between two Route Points, which are served by the vehicle with trailer. If the new customer can be served by vehicle with trailer as well, then it is Unload Point insertion. Otherwise, there are two options possible - the program can insert one of Leave Points, then Unload Point and Take Trailer Point. The program chooses one of the two options with some probability, however, Leave Trailer With Unload Point may happen not in every such case, that is why, there is special test for this option. The code of Trailer Point insertion is following:

if (isTrailerPoint(route.get(place).getType(),route.get(place + 1).getType()))

{

if (vrp.isTruckStore(vehicle,customer))

{

float decision = (float) config.generator.nextDouble();

if (!isPossibleToLeaveTrailer(route.get(place).getType()))

decision = 0;

if (decision < 0.5)

{

success = leaveTrailerWithoutUnloadInsertion(customer, iter, unloadTime, totalCargo);

if (success)

{

route.add(place + 1, new LeaveTrailerWithoutUnloadPoint());

route.add(place + 2, new UnloadRoutePoint());

route.add(place + 3, new TakeTrailerPoint());

currentInsertionPlace = place + 2;

}

return success;

}

else

{

if (totalCargo > vehicle.getTrailerCapacity())

return false;

RoutePoint unloadPoint = route.elementAt(place);

LeaveTrailerWithUnloadPoint leaveTrailerPoint = new LeaveTrailerWithUnloadPoint();

leaveTrailerPoint.setLoad(unloadPoint.getHotLoad(),unloadPoint.getFreezeLoad());

Customer leaveTrailerCustomer = route.elementAt(place).getCustomer();

success = leaveTrailerInsertion(leaveTrailerCustomer, customer, iter, unloadTime, totalCargo);

if (success)

{

route.remove(place);

route.add(place, leaveTrailerPoint);

route.add(place + 1, new UnloadRoutePoint());

route.add(place + 2, new TakeTrailerPoint());

currentInsertionPlace = place + 1;

}

return success;

}

}

else

{

success = simpleParkingUnloadInsertion(customer,iter,unloadTime,totalCargo);

if(success)

{

route.add(place + 1, new UnloadRoutePoint());

currentInsertionPlace = place + 1;

}

return success;

}

}

The full code of all insertion cases procedures in Application 1.

The greedy algorithm structure also has slightly changed. The change is caused by the new procedure for determining the number of allowed delays in route. In old architecture, every delay added a penalty to the cost of the route. If the final solution exceeded the limit of delays, then the solution was marked as infeasible. As a result, a lot of solutions in old architecture were discarded and the problem of finding the right penalty cost was sufficient. However, in the new architecture, the goal is to obtain one feasible solution. That is why, for every route, special procedure determines the number of delays, which are allowed for the route to make.

The procedure code looks like this:

boolean canDelay()

{

if (remainingDelays < 1)

return false;

double expectedDelays = ((double) maxExpectedDelayNumber * (double)(hungryCustomers.size() + 1) / actualCustomersNumber);

return (config.generator.nextDouble() < (((double)remainingDelays) / expectedDelays));

}

Maximum expected delay number - is a variable, which reflects, how many delays the algorithm will do if there is no constraint on the number of delays. Hungry customers - is the list of unserved customers, actual customers number - is the number of unserved customers before the start of the whole algorithm. Remaining delays - it is the number of delays that is allowed to do at this moment for the whole solution. If the procedure returns true, the number of allowed delays increases by 1 and number of remaining delays for the whole solution decreases by 1. The procedure is called while it returns true. The procedure is fair in a sense that the number of allowed delays for every route does not depend on the number of the route. Let's consider an example of another formula:

expectedDelays = delayLimitPercent * actualCustomersNumber

where delay limit variable is the percent of delays under the constraint, for example, if 20% delays allowed, delayLimitPercent = 0.2. Then, basically, at the start of greedy route construction algorithm, number of expected delays is equal to the number of remaining delays. That will lead to the situation, when routes, which are constructed first, have a lot of allowed delays, while routes that are constructed last would be required to have no delays. This is wrong not only because of unfairness, but because some customers cannot be served without delay, and some of those customers are served in last constructed routes.

The whole greedy route construction algorithm is also changed. For every insertion of new customer, the algorithm considers two variants of insertion - insertion with delay and insertion without delay. For every variant, the algorithm remembers the best insertion. After the algorithm checks all possible insertions, there are two newly constructed routes - one with delays and one without delays. The choice of best route from these two options is based on the cost of routes. The pseudocode for greedy route construction algorithm in the new program architecture is the following:

Greedy route construction algorithm (new architecture)

firstCustomer = findDistantCustomer()

vehicle = findProperVehicle(firstCustomer)

route = constructRoute(vehicle,firstCustomer)

delays = findNumberOfAllowedDelays()

while(true)

bestDelayedRoute = null

bestNonDelayedRoute = null

for every customer in customersList

delayedRoute = tryCustomerInRouteWithDelays(customer,route)

if delayedRoute is better than bestDelayedRoute

bestDelayedRoute = delayedRoute

nonDelayedRoute = =tryCustomerInRouteWithoutDelays(customer,route)

if nonDelayedRoute is better than bestNonDelayedRoute

bestNonDelayedRoute = nonDelayedRoute

if bestDelayedRoute != null || bestNonDelayedRoute != null

route = chooseBestCost(bestDelayedRoute, bestNonDelayedRoute)

else

end GreedyRouteConstructionAlgorithm

3.3.2 Algorithm of deletion and heuristic with tabu search elements

As it was described above, local search and tabu search needs neighborhoods and for SDTTRPTW problem with soft time windows and split deliveries, so-called moves allow the solution to travel through solution's neighborhood. The move consists from deletion of the customer from one route and insertion in other route. Earlier, the idea of the new architecture is to provide equality of operations of insertion and deletion. Indeed, operation of deletion is quite similar to the operation of insertion.

The deletion operation is divided in three subcases:

1) Simple deletion of Unload Point. In this case the program deletes just one Unload Point from the sequence of Route Points along with the corresponding actions.

2) Deletion of Unload Point inside of truck subtour. If the program deletes an Unload Point, there is a possibility that route does not need the truck subtour anymore. For example, it happens if the program deletes customer that corresponds to the second Route Point in sequences Leave Trailer Without Unload Point - Unload Point - Take Trailer Point or Leave Trailer With Unload Point - Unload Point - Take Trailer Point. Then, first sequence should be deleted entirely, second sequence is converted to one Unload Point, that corresponds to customer from Leave Trailer With Unload Point.

3) Deletion of Route Point that is “responsible” for subtour. In this case the algorithm chooses to delete the same customer, where the trailer is left. Basically, in this case, the program needs to delete Leave Trailer Point and Take Trailer Point, and add new such points after choosing the new “responsible” customer. Usually, new customer to leave trailer is chosen as the first customer of truck subtour that is left. If this new customer can be served by the vehicle with trailer, the program creates Leave Trailer With Unload Point for this customer, otherwise, the program creates Leave Trailer Without Unload Point.

The code of deletion of one Route Point is following:

ListIterator<Action> deleteRoutePoint(int place) throws ActionConstructionException

{

int actionIndex = 0;

for (int i = 0; i < place; i++)

actionIndex += route.elementAt(i).getLength();

ListIterator<Action> iter = actions.listIterator(actionIndex);

int length = route.elementAt(place).getLength();

for (int j = 0; j < length; j++)

{

iter.next();

iter.remove();

}

Customer prevTravelCustomer = vrp.customers.elementAt(0);

Customer nextTravelCustomer = vrp.customers.elementAt(0);

if (route.elementAt(place - 1).getType() != RoutePointType.DEPOT)

prevTravelCustomer = route.elementAt(place - 1).getCustomer();

if (route.elementAt(place + 1).getType() != RoutePointType.DEPOT)

nextTravelCustomer = route.elementAt(place + 1).getCustomer();

int timeToStart = -300;

if (iter.hasPrevious())

{

int pos = iter.previousIndex();

timeToStart = actions.get(pos).finishAt();

}

Travel travel = new Travel(prevTravelCustomer,timeToStart,nextTravelCustomer,vrp);

iter.next();

iter.remove();

iter.add(travel);

return iter;

}

After the deletion, the deleted customer should be inserted in one of the other routes. The code for all deletion cases in the Application 2.

In local search and tabu search, to find the best move, the program should try all possible moves. However, the full search through possible moves is time-consuming. Because of that, in the program, it was decided to use another scheme. The route, from which the program tries to delete customer, is chosen randomly. The customer to delete from this route is also chosen at random. If the operation of deletion is successful, the program tries to insert the deleted customer in other routes. However, the places to insert the customer are chosen in such way, that at least one of the new neighbors in the other route be close to the deleted customer. Then, the best possible insertion is found by the criteria of total cost plus penalty.

Using this scheme, the program does not need the list of tabu moves. Sure enough, if the program performed a move with customer X, the probability that at the next step of tabu search the program will perform reverse move is close to , where n is the number of customers. So, on average, the tabu search will try to make a move with a lot of other customers before it returns to the customer X.

For the tabu search neighborhood extensions, the constraint on total number of delays and the constraint on the capacity of vehicle were chosen. It means that the program may perform moves that increase total number of delays over the limit and moves that make total delivery in the route more than the capacity of the vehicle in the route. However, experiments showed that there should be limit on these moves. Basically, the number of delays may exceed the limit only by some value and the number of over-capacitated routes should be limited. Moreover, if the performed move adds excessive delays or over-capacitated routes, the cost of the move is calculated as the basic cost delta plus penalty on excessive delays plus penalty on over-capacitated route. The penalty on over-capacitated route also depends on the total weight of cargo that exceeds vehicle capacity.

penaltyCost(route1, route2, route3, route4) procedure

//route1 - route with deleted customer before the operation of deletion

//route2 - route with deleted customer after the operation of deletion

//route3 - route to insert deleted customer before the operation of insertion

//route4 - route to insert deleted customer after the operation of insertion

costDelta = cost(route2) + cost(route4) - cost(route1) - cost(route3)

delayDelta = delays(route2) + delays (route4) - delays (route1) - delays (route3)

if delayDelta + currentDelays > delayLimit + tabuDelayLimit

return BIG_NUMBER

delayPenalty = penaltyForDelays(delayDelta + currentDelays)

deltaInNumberOfOverCapacitatedRoutes = overCapacity(route2) + overCapacity (route4) - overCapacity (route1) - overCapacity (route3)

if deltaInNumberOfOverCapacitatedRoutes + +currentNumberOfOverCapacitatedRoutes > tabuOverCapacitatedLimit

...