README.md

Heuristics-SDHFFVRPTWSD

Heuristics developed to tackle the Site Dependent Heterogeneous Fixed Fleet Vehicle Routing Problem with Time Windows and Split Deliveries.

Usage

Simply run the .py files with the algorithm of choice or import their main functions with the same name as the files. Make sure all the following parameters are available:

Classes:

• vehicles: must contain capacity a (float), freight cost cf (float) and site dependency matrix (R[vehicles x customers] (int)).
• customers: must contain demand q (float), minimum start time e (float), service time s (float) and maximum ending time l (float).
• individuals: must contain routes, partial_demandsand wait_times as generated by the Clarke-Wright algorithms.

Matrices:

• distances d: matrix [customers x customers] of distances between two customers or depot (int).
• travel time t: matrix [customers x customers] of travel time between two customers or depot (float).

Algorithms

Clarke-Wright for the SDHFFVRPTWSD

Based on the Clarke-Wright (1964) savings heuristic, the files clarke_wright_series.py and clarke_wright_paralell.py are my first approaches on tackling the SDHFFVRPTWSD with a constructive heursitic. The clarke_wright.py file has the best approach tailored to tackle the problem.

Series Clarke-Wright

This algorithm iteratively merges routes until the vehicle capacity is exceeded; only then, another route is created if there are available vehicles. Thus, it is best suited for instances which the freight cost spread is high and it is very important to get the best possible route to the vehicles with least freight cost. The pseudocode below describes the general procedure.

1.  calculate savings for each pair of clients
2.  sort savings in descending order of saving
3.  routed_customers <- Ø
4.  final_routes <- Ø
5.  WHILE there are available vehicles DO:
6.      route <- Ø
7.      load = 0
8.      vehicle = available vehicle with the least freight cost
9.      WHILE possible DO:
10.         IF route is empty:
11.             start route with feasible candidate from the best unrouted savings pairs
12.            IF there is no feasible candidate:
13.                BREAK WHILE
14.            ELSE:
15.                 load += unserviced demand of the last customer
16.                 set last customer = candidate
17.             ENDIF
18.         ELSE:
19.             FOR (i, j) in sorted savings pairs DO:
20.                 IF either i or j are either the first or last customers and the new route is feasible:
21.                     merge route with [0,i,0] or [0,j,0]
22.                     load += unserviced demand of of the last customer
23.                     set last customer = i or j
24.                     BREAK FOR
25.                 ELSE:
26.                     CONTINUE
27.             ELSE:
28.                 BREAK WHILE
29.             ENDFOR
30.         ENDIF
31.         IF load > vehicle capacity:
32.             serviced demand = unserviced demand - (load - vehicle capacity)
33.             unserviced demand -= serviced demand
34.             f[vehicle][last customer] = serviced demand / total demand
35.             BREAK WHILE
36.         ELSE:
37.             f[vehicle][last customer] = unserviced demand / total demand
38.             unserviced demand = 0
39.         ENDIF
40.     ENDWHILE
41.     FOR each customer DO:
42.         IF unserviced demand of the customer == 0:
43.             add customer to the routed_customers
44.         ENDIF
45.     ENDFOR
46.     add route to final routes and assign the vehicle for it
47.     remove the vehicle from available vehicles
48. ENDWHILE
49. RETURN final routes and f matrix

Paralell Clarke-Wright

This algorithm iteratively merges single customers with the existing routes and creates new routes when the merge is not possible with the existing ones. The objective is to make best use of the highest savings pair of customers. The pseudocode below describes the general procedure.

1. calculate savings for each pair of clients
2. sort savings in descending order of saving
3. unserviced_demands <- Ø
4. fully_serviced <- Ø
5. routes <- Ø
6. available_vehicles <- vehicles
7. WHILE there are customers with unserviced demands DO:
8.     FOR (i, j) in sorted savings pairs DO:
9.         IF there are available_vehicles without a route:
10.            IF either i or j belongs to a route and both not to the others:
11.                route = route from routes containing either i or j
12.                vehicle = vehicle for which the route was assigned
13.                IF the vehicle is full:
14.                    CONTINUE
15.                ENDIF
16.                IF either i or j are either the first or last customers and the new route is feasible:
17.                    merge route with [0,i,0] or [0,j,0]
18.                    update route in the routes list
19.                    load[vehicle] += unserviced demand of the merged customer
20.                    set last customer = merged customer
21.                    BREAK FOR
22.                ENDIF
23.            ELSE IF neither i nor j belong to an existing route:
24.                vehicle = available vehicle with minimum freight cost
25.                start route with either i or j
26.                IF neither is feasible:
27.                    CONTINUE
28.                ENDIF
29.                remove vehicle from available_vehicles
30.                add route with vehicle to the routes list
31.                load[vehicle] += unserviced demand of the feasible candidate
32.                set last customer = feasible candidate
33.                BREAK FOR
34.            ENDIF
35.        ELSE:
36.            IF either i or j belongs to a route and both not to the others:
37.                same merging procedure as when there were available_vehicles
38.            ENDIF
39.        ENDIF 
40.    ELSE:
41.        BREAK WHILE
42.    ENDFOR
43.    IF load[vehicle] > vehicle capacity:
44.        serviced demand = unserviced demand[last customer] - (load[vehicle] - vehicle capacity)
45.        unserviced demand[last customer] -= serviced demand
46.        f[vehicle][last customer] = serviced demand / total demand
47.        mark vehicle as full so it cannot be routed anymore
48.    ELSE:
49.        f[vehicle][last customer] = unserviced demand / total demand
50.        unserviced demand[last customer] = 0
51.    ENDIF
52. ENDWHILE
53. RETURN routes and f matrix

Paralell Clarke-Wright with Starting Criterium

Previous paralell Clarke-Wright with a restriction criterium to start route: customers that can be serviced with less vehicles are chosen to start the routes for the vehicles that can service them. If there is a draw, the customer with a smaller time window is routed first. If there is another draw, the criterium takes the customer with the least demand (so its service does not affect significately the vehicle's capacity). The algorithm also handles concomitances of two or more vehicles in the same customer with waits, but the time feasibility in with concomitance correction is not guaranteed. The pseudocode below describes the general procedure.

1. calculate savings for each pair of clients
2. sort savings in descending order of saving
3. unserviced_demands <- Ø
4. fully_serviced <- Ø
5. routes <- Ø
6. available_vehicles <- vehicles
7. WHILE there are customers with unserviced demands DO:
8.     IF there is at least a vehicle without a route assigned to it:
9.         chose the customer j with most restrictions (R, time windows, least demand)
10.        IF the route [0,j,0] is feasible for the vehicle that can service j:
11.            IF the vehicle was not yet assigned to a route:
12.                add [0,j,0] to routes and assign the vehicle for it
13.            ENDIF
14.        ENDIF
15.    ELSE:
16.        FOR (i, j) in sorted savings pairs DO:
17.            IF either i or j belongs to a route and both not to the others:
18.                route = route from routes containing either i or j
19.                vehicle = vehicle for which the route was assigned
20.                IF the vehicle is full:
21.                    CONTINUE
22.                ENDIF
23.                IF either i or j are either the first or last customers and the new route is feasible:
24.                    merge route with [0,i,0] or [0,j,0]
25.                    update route in the routes list
26.                    load[vehicle] += unserviced demand of the merged customer
27.                    set last customer = merged customer
28.                    BREAK FOR
29.                ENDIF
30.            ENDIF
31.        ELSE:
32.            BREAK WHILE
33.        ENDFOR
34.    ENDIF
35.    IF load[vehicle] > vehicle capacity:
36.        serviced demand = unserviced demand[last customer] - (load[vehicle] - vehicle capacity)
37.        unserviced demand[last customer] -= serviced demand
38.        f[vehicle][last customer] = serviced demand / total demand
39.        mark vehicle as full so it cannot be routed anymore
40.    ELSE:
41.        f[vehicle][last customer] = unserviced demand / total demand
42.        unserviced demand[last customer] = 0
43.    ENDIF
44. ENDWHILE
45. wait <- Ø
46. get start time for each customer assuming no wait
47. IF there is concomitance between two consequent vehicles:
48.     calculate the remaining service time for the first vehicle to arrive and add it to the wait of the next vehicle
49. ENDIF
50. IF there is time infeasibility due to the wait:
51.     try swapping the customer in the last consequent vehicle with the previous customer in its route
52.     IF the route is still infeasible:
53.         return previous route and wait
54.     ELSE
55.         update routes and recalculate wait
56.     ENDIF
57. ENDIF
58. RETURN routes, f matrix and wait matrix

Clarke-Wright Randomized

An additional Clarke-Wright algorithm is used to generate multiple solutions. The clarke_wright_randomized function generates a population of feasible and infeasible (for time-windows or site depedency) solutions in a similar way as in the first steps of a GRASP algorithm. To do that, instead of picking the best pair according to savings, a random pair is chosen according to the harmonic distribution, so that pairs with greater saving have a probability of being picked two times greater than the next pair of savings. If a solution generated has underservice, it is discarded.

Genetic Algorithm

This is a Genetic Algorithm applied to the SDHFFVRPTWSD. It uses the clarke_wright_randomized to generate the initial population and runs an evolutive process until a criterium is met (convergence or fixed number of iterations). The parents are couples of individuals selected using SUS selection based on a cost function that takes into consideration weighted infeasibilities. The offspring is generated by the ctr_crossover operator which determinates the best and worst routes of each parent (dividing total distance by number of routes), taking only the former to construct the offspring and excluding the latter. The mutation operator simply swaps a customer with the next on its route, on a certain fraction of the offspring. There is a mechanism to preserve the best solutions which avoids taking the p_elite best solutions to the survival phase. The latter reduces the size of the population back to population_size SUS-selectin the survivors in a similar way as in the sus_selection. Finally, when the criterium is met the GA returns the best individual, containing routes and partial demands lists.

1.  generate initial population using clarke_wright_randomized(size)
2.  population <- initial_population
3.  WHILE criterium is unmet DO:
4.      WHILE size(population) < 2*size DO:
5.          parents <- sus_selection(population)
6.          offspring <- ctr_crossover(parents)
7.          offspring <- crrm_mutation(offspring, mutation_rate)
8.          population = parents + offspring
9.      ENDWHILE
10.     population_elite <- elite(p_elite, population) 
11.     population = population \ population_elite
12.     population <- sus_survival(population)
13.     population = population + population_elite
14.     evaluate criterium
15. ENDWHILE
16. return best individual from population