Heuristic Approaches for a Dual Optimization Problem

1. Introduction

The current crisis in the global economy and the stiff competition has led many firms to recognize the importance of managing their logistic network for organizational effectiveness, improved customer value, better utilization of resources, and increased profitability. The logistics business in Spain continues rising mainly by the new electronics market. In 2008 the turnover of logistics activities was 3.745 m€, 1.5% compared to previous year. Despite the upward trend, the strategic sector analysis done by DBK shows that the problem of declining business performance of the sector is as a result of rising fuel prices. The same study claim that the industry is in a process of concentration, with the disappearance of small operators (DBK (2009)). This requires that firms need to optimize its efficiency, e.g. recalculating the routes in order to minimize costs. To reduce the logistics costs related to transportation routes is a goal sought by all firms, where the transportation costs are easily controlled in the value chain.

There is a difference between national and international transport by road, and the distribution within the city and its close environment (widespread distribution). It has been more important in nowadays, where many firms need to do their deliveries at close proximity. However, when transportation at national and international levels is involved, more benefits can be achieved by a good planning strategy. The national and international transport by road, e.g. transport between urban centres, requires large vehicles carrying its maximum load. A good route planning can reduce the costs significantly, especially when the increasing in oil prices makes any unnecessary kilometre a profit to the company.

In Spain there are approximately 225 logistic firms, but only 4 of them have the majority of market (more than 40% of the total). In this study the biggest one, with 3577 vehicles and 411 great vehicles, has been considered. The company is focused on the distribution into cities by road. The routes are interconnected through ships, i.e. a high capacity logistic centres that are strategically located. The company has designed its domestic routes based on its own experience. This paper presents a meta-heuristic method that determines the routes that involve the major number of cities in order to increase flexibility, leading the vehicle deliver and pick up in these cities, trying to minimize the distance travelled and its costs.

The problem can be approximated to a series of problems similar to the travel salesman problems (TSP), and therefore a vehicle routing problem, with time windows (VRPTW). VRPTW tries to find a final solution including sub-path not connected and that meet the constraints of the TSP considering the time windows constrains. The restrictions of Miller et al. (1960) have been used in order to reduce the computational cost. The main purposes of the method are to provide a quick solution and flexible enough to be used in a dynamic scheduling environment, and to develop a new solution procedure that is capable of exploiting the special characteristics of the problem.

Drawing upon the state of the art presented in next section is developed a recurrent neural network approach, which involves not just unsupervised learning to train neurons, but an integrated approach where Genetic Algorithm is utilized for training neurons so as to obtain a model with the least error.

The paper is organized as follows. Section 2 elaborates on the problem faced along with the considered case study. Section 3 describes TSP modelling for the problem and a brief state of the art on VRP and applied heuristics. Section 4 provides the working of heuristics and computational experience for the recurrent neural network approach and genetic algorithm, and finally Sections 5 and 6 explain the results and conclusion respectively.

2. Case study

2.1. Background

The main problem is the profitability of routes for the logistic companies. This research paper analyses cases where a direct route between two cities minimize the distances, but it should not be considered from the cost point of view because the shipping volume is not significant enough. On the other hand, with a significant shipment, it is economically more profitable that when only the distance between two cities are considered. Therefore the transport logistics should be designed considering the service effectiveness.

The main objective is to satisfy the customers with greater effectiveness and efficiency, especially with the competence. Routes are constructed to dispatch a fleet of homogenous or heterogeneous vehicles to service a set of customers from a single distribution depot. Each vehicle has a fixed capacity and each customer has a known demand that must be fully satisfied. The objective is to provide each vehicle with a route that maximize the cities visited and the total distance travelled by the fleet (or the total travel cost incurred by the fleet), minimising the costs.

The problem is characterized as follows: From a principal depot the products must be delivered in given quantities to certain customers. A number of vehicles with different capacities are available. All the vehicles that are employed in the solution must cover a route, starting and ending at the principal depot, and the products are delivered to one or more customers in the route. The problem consists in determining the allocation of the customers among routes and the sequence in which the customers shall be visited on a route. The objective is to find a solution which minimizes the total transportation costs. Furthermore, the solution must satisfy the restrictions that every customer is visited exactly once in the capillary routes where the demanded quantities are delivered, but it is not necessary for the principal route. The transportation costs are specified, where the costs are not necessarily identical in the two directions between two cities.

In this paper the meta-heuristics method of the recurrent neural network is proposed to solve the dual problem, in order to increase the flexibility in the routes and minimizing costs. The following considerations have been considered:

• The principal route will be covered by a large-capacity truck. For practical purposes, it will be considered a big commercial vehicle.

• Capillary routes (routes between a principal city and the near small cities) will be covered by trucks of medium / small capacities, considered a light commercial vehicle.

• The First-Input-First-Output (FIFO) method is followed when multiple vehicles are present to transhipment transport.

• The fuel consumption is taken as an average value of 30 litres per 100 km for a big vehicle, and 15 litres per 100 km for a light commercial vehicle.

• The diesel price is fixed as 1 € / litre.

• The maximum speed considered are the legally permissible for a vehicle of these characteristics according to the Spanish laws.

2.2. Principal and capillary routes

A real case study has been considered, which the principal route consists in determining the route for sending a product set from Barcelona to Toledo (Spain). The route considered by the company is:

Main Route 1: Barcelona-Madrid; Main Route 2: Madrid-Toledo; Capillary route: Toledo- different towns close to Toledo.

The Madrid-Barcelona route is the same to the Barcelona-Madrid. The total distance is 1223 km, and the time estimated is 14 hours and 41 minutes, with a total cost of 366.93 €.

A first approach in this case study is to employ a route which passes through the maximum number of cities as possible minimizing costs, with the objective of maximise the flexibility. It will lead to the vehicle pick up or deliver products in those cities.

A big capacity vehicle covers this route, denoted as 'vehicle A', leaving the origin city with a certain quantity of product. If there is excess of products, they will be transported by other vehicles.

The solution proposed by the company is: Vehicles follow the route assigned to arrive in Madrid. The vehicles are unloaded and are available to be loaded again. The vehicles leave for Barcelona and the availability of products in order to fill the vehicles is not assured. The vehicle A must to wait to be fill, creating waiting time that increases the logistic costs. The vehicle A can be then loaded for shipment to Cuenca (an intermediate city), and other trucks that make the route Cuenca-Madrid-Cuenca are unloaded in Madrid.

The vehicle A will serve as a logistical support, which means that normally it will be loaded partially. It will be loaded completely in Teruel (city in the middle of the route). The products will be unloaded in Cuenca, first destination from Madrid, and then loaded with new products to be shipped in Teruel, next destination before to arrive to Barcelona, last destination. The same process followed for the city of Cuenca is applicable to the city of Teruel as it has been abovementioned.

This procedure done by the logistic company justifies the need of visiting the maximum number of logistic cities in any route. But if the vehicle visits many cities appears delay problems or the increasing of the costs.

When the vehicle arrives from Madrid to Toledo (a direct route that will not be considered in the dual problem), the products require to be served in different towns close to Toledo. It is done following capillary routes.

The case study considers a new vehicle that visits ten towns, starting and finishing in Toledo. In any town that is visited the vehicle need to deliver and to pick up products according to the orders processed in the previous day (for delivery) or in any specific day (in the case of pick up). The assigned route by the company is:

Toledo → Torrijos → Bargas → Mocejón → Añover de Tajo → Recas → Yuncos → Illescas → Esquivias → Fuensalida → Toledo.

The total distance covered is 209.9 km, and the time is 2 h 41 min.

In this paper a solution is found out for the dual problem, maximizing the logistic centres visited and minimizing the distance covered, considering the restrictions of the current time and costs given by the company.

3. Dual problem formulation

3.1. Travelling salesman problem (TSP) approach for the primary distribution

TSP consists in finding a route with the shortest distance that visit all the nodes (cities) and only once each, starting in a city and returning to the starting city (Nilsson, 1982). TSP has been very important because the algorithms developed to solve it do not guarantee to solve it with optimality within reasonable computational cost. Therefore a great number of heuristics and heuristics algorithms have been developed to solve this problem in approximately form. TSP is a NP-hard problem in combinatorial optimization that requires finding a shortest Hamiltonian tour on n given cities (Lawler et al. 1985; Gutin and Punnen 2002). Cities are represented by nodes in a graph, or by points in the Euclidean plane. The distances between n cities are stored in a distance matrix D with elements d_ij, being d_ij the distance between cities i and j, where the diagonal elements d_ii are zero, i.e. there is not distance between a city and itself. A common assumption is that the triangle inequality holds, that is d_ij ≤ d_ik+ d_kj, ∀ i,j,k = 1,…,n. Also, the symmetrical assumption, d_ij=d_ji, it is the same distance from i to j than from j to i. A review of previous works on TSP using different heuristics is provided in Table 1.

Methods	References
Branch-and-bound	Finke et al. (1984); Little et al. (1989); Balas and Toth (1985); Miller and Pekny (1989)
2-opt	Lin and Kernighan (1973); Bianchessi and Righini (2007); Gendreau et al. (1999); Potvin et al. (1996); Tarantilis (2005); Tarantilis and Kiranoudis (2007); Verhoeven et al. (1995)
Insertion	Breedam (2001); Chao (2002); Daniels et al. (1998); Lau et al. (2003); Nanry and Barnes (2000)
Neural network	Shirrish et al.(1993); Burke (1994)
Simulated annealing	Kirkpatrick et al.(1985); Malek et al. (1989); Osman (1993)
Tabu search	Glover (1990); Gendreau et al. (1996); Gendreau et al. (1998); Ahr and Reinelt (2006); Augerat et al. (1998); Badeau et al. (1997); Brandao and Mercer (1997); Barbarosoglu and Ozgur (1999); Garcia et al. (1994); Semet and Taillard (1993); Hertz et al. (2000); Montane and Galvao (2006); Scheuerer (2006)
Exact methods	Carpaneto and Toth (1980); Fischetti and Toth (1989); Gouveia and Pires (1999); Lysgaard (1999); Wong (1980)
Genetic Algorithm	Gen and Cheng (1997); Potvin (1996); Moon et al.(2002)

Table 1.

Literature summary: different heuristic methods for solving TSP.

The heuristics algorithms developed for solving the TSP presents low computational cost and provides solutions near to the optimal. Different approaches have leaded different formulations for solving the TSP as a linear programming problem, with integer/mixed integer variables (Lawler et al., 1985, and Junger et al., 1997). Many managerial problems, like routing problems, facility location problems, scheduling problems, network design problems, can be modelled as TSP. A great number of articles have appeared with detailed literature reviews for TSP, e.g. Bellmore and Nemhauser (1968), Bodin (1975), Golden et al. (1975), Gillett and Miller (1974), and Turner et al. (1974).

The problem presented in this paper is formulated as a TSP approach for the principal distribution with the travel cycle known as a Hamiltonian cycle, i.e. the problem is defined by the graph G = (V, E), where V∈ℜ² is a set of n cities, and E is a set of arcs connecting these cities, but in this approach the cities can be visited more than once. Under these conditions, the problem can be formulated as:

Minimize:

$${\displaystyle \sum _{i<k}{c}_{ij}{x}_{ij}},$$E1

where $$x_{ij}$$is the binary decision variable that when i < j has the following values:

$$x_{ij}\{\begin{array}{c}\text{1 if the arc joining cities i and j is used in solution}\\ \text{0 otherwise}\end{array},$$

subject to the constraints:

$${\displaystyle \sum _{i<k}{x}_{ik}+}{\displaystyle \sum _{j<k}{x}_{kj}}=2,$$E2

$$k=1,2,\dots n,$$E3

$${\displaystyle \sum _{i,j\in S}{x}_{ij}\le \left|S\right|}-1,$$E4

$$\begin{array}{l}S\subset V,3\le \left|S\right|\le n-3,x_{ij}\in \left\{0,1\right\},\\ i,j=1,2,\dots n,i<j,\end{array}$$E5

being equation 1 the objective function. C is the associated cost matrix to the matrix E, compounds by the elements c _ij that represents the “distance” (expressed in physical distance, cost, time, etc.) between the cities i and j, where c_ij ≤ c_ik + c_kj for all i,j∈V, to be Euclidean. The constraints ensure that:

1. All cities are connected to each other

2. Elimination of sub-path S since the sub-path should not be defined for ∣S∣=2 and ∣n-2∣ because restrictions (iii) and (iv) ensure that between two cities no sub-path is generated.

The model (1) contains n (n-1) binary variables, with 2n constraints and 2ⁿ - 2(n-1) sub-path constraints that need to be removed, making it very complex and computational costly. The restrictions proposed by Miller et al. (1960) have been considered which can reduce the number of sub-path, also referred to as disposal restrictions. In these new restrictions is necessary to consider the new variables u_i (i = 2,..., n) given by:

$$u_i-u_j+\left(n-1\right)x_{ij}\le n-2,i,j=2,\dots n,i\ne j,$$E6

$$1\le u_i\le n-1,i=2,\dots n.$$E7

The restriction (1.v) indicates that the solution does not contain a sub-path in all cities S⊆V and all sub-path contains more than n cities. The restriction (1.vi) ensures that the u_i variables are defined only for each sub-path. This formulation has been employed for solving the principal distribution, e.g. the transport between the cities of Barcelona and Madrid, considering the main cities between them, where it is possible to visit a city more than once.

TSPs can also be represented as integer and linear programming problems. In this paper it will employed for the capillary formulation problem. The integer programming (IP) formulation is based on the assignment problem with additional constraint of no sub-tours:

$$\min {\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^n{c}_{ij}{x}_{ij}}}$$E8

$$\text{s}\text{.t}\text{.}{\displaystyle \sum _{i=1}^n{x}_{ij}=1}\text{for all }j$$E9

$$\begin{array}{l}{\displaystyle \sum _{j=1}^n{x}_{ij}=1}\text{for all }i\\ x_{ij}\in \left\{\text{0,1}\right\}\text{for all }i\text{,}j\end{array}$$E10

where (2) is the objective function and the constraints (3) and (4) ensure that each city is visited exactly once. TSP can be also expressed as a linear programming (LP) formulation by the equation (5).

$$\begin{array}{l}\text{Minimize }{\displaystyle \sum _{\text{i}=\text{1}}^{\text{m}}{w}_i{x}_i}=w^{T}x\\ \text{Subject to x}\in S\end{array}$$E11

where m is the number of edges in G, w_i is the weight of edge and x is the incidence vector that indicates the presence or absence of each edge in the tour. There are a number of algorithms used to find optimal tours, but none are feasible for large instances since they all grow exponentially. This formation has been employed for solving the capillary route problem.

3.2. Vehicle route problem

The transport problem is formulated in this paper as the travel salesman problem (TSP) adapted to the real case study, adding different routes to the final route. Therefore it will be considered as a VRP problem.

The VRP has been considered in many research works in the last few years. Evans and Norback (1985) designed an heuristic-based decision-support system, which utilizes computer-graphic pictures of routes in a large service distribution. The system provides scheduler of routes with a tool to enable the rapid evaluation of computer-proposed solutions and to easily modify them.

Faulin (2003) employed the MIXALG method, combining heuristic algorithms and linear programming routine, as a way of solving routing problems with moderated size. This method is efficient because does not consider some burdensome procedures in unnecessary situations. The initial solutions for linear programming have been found by a Clarke–Wright variant method that considers the logistic cost reduction as one of the main conclusions.

Hsu and Feng (2003) studied the distribution using a VRP with time windows (VRPTW), and they solved the problem by the Time-Oriented Nearest-Neighbor Heuristic method. Huey-Kuo et al (2009) employed a nonlinear mathematical model, based on the constrained Nelder–Mead method and a heuristic algorithm, for a VRPTW, with the objective of maximising the expected total profit of the supplier setting the optimal production quantities, the time to start producing and the vehicle routes. Loannou et al. (2001) solved the VRPTW using a heuristic method based upon Atkinson's greedy look-ahead heuristic.

Ma et al. (2012) solved a vehicle routing problem with time windows and link capacity constraints (VRPTWLC). They employed a tabu search heuristic with an adaptive penalty mechanism (TSAP).

Prins (2004), contrary to the VRPTW, concludes that no genetic algorithm can compete with the tabu search (TS) methods designed for the VRP. Prindezis et al. (2003) developed an Application Service Provider to coordinate and disseminate tasks and related spatial and non-spatial information for solving the VRP. A similar case was solved by Gendrau et al. (2006) employing TS. In 2004, Tarantilis et al. employing a metaheuristic algorithm called BoneRoute, for solving the open vehicle routing problem (OVRP). The OVRP deals with the VRP problem without returning to the distribution centre. The VRP with backhauls (VRPB), where deliveries after pickups are not allowed is solved by Tütüncü et al. (2009). The authors extended the formulation to a mixed VRPB where deliveries after pickups are allowed. A new criterion, which considers the remaining capacity of the vehicles, is proposed to find solutions for mixed and restricted VRPB. They solved the problem a greedy randomised adaptive memory programming search (GRAMPS) algorithm.

The problem was formulated by Tarantilis and Kiranoudis (2001) as an open multi-depot vehicle routing problem (OMDVRP). It was solved by a stochastic search meta-heuristic algorithm termed as the list-based threshold accepting (LBTA) algorithm. The proposed routing plan gives answers to a number of operational decision problems and provides significant economic benefits for the company. An extension of this study was presented in Tarantilis and Kiranoudis (2002).

4. Recurrent neural network and genetic algorithm approaches (RNNGA)

Neural networks (NN) represent the operating mechanism of the human brain, based on a fair degree of some simple computational nodes called neurons. The knowledge is acquired through a learning process, and the connection interneuron (synaptic weights) would be used for the storage of knowledge. Artificial NN are networks comprising of large quantities of highly interconnected simple computational elements. They use data from previous steps incorporating information from multiple indicators, being a non-parametric model (Alekxander and Morton, 1990). Time and data are required for learning and training the network. Once the network is trained and completed, it can determine feasible solutions to similar problems. Figure 1 shows the structure of a NN where each neuron receives information from neurons that are found in a layer closer to the input layer, and sends the output to a layer that is closer to the output layer. The types of links in the NN consist of synaptic and activation links, and the way in which neurons in the network structure are assigned determines its architecture. NN are non-linear statistical data modelling tools used to model complex relationships between inputs and outputs or to find patterns in data. Recurrent Neural Network (RNN) refers to a special type of neural network where the output of previous iteration is used as an input for the next iteration. There are many systems in the real world whose behaviour depends on their current state, such systems can be modelled by RNN. When the NN is applied to problems involving nonlinear dynamical or state dependent systems, NN with feedbacks can in some cases provide significant advantages over purely feed forward neural network (FNN).

There are some input neurons and one feedback neuron. The feedback neuron takes previous iteration’s output as input while the other neurons take a fixed input. The output of the input layer is passed to hidden layer; output of interaction of hidden layer neurons is passed to the output, therefore it gets an output. The associated weights are calculated by applying some algorithm, e.g. back propagation using gradients. In this research work a genetic algorithm (GA) is used to determine the weights.

Back propagation method using gradients for training has been successfully applied to FNN (Bourlard and Wellekens 1989, Le Cun et al. 1989, Sejnowski and Rosenberg 1987, Waibel et al. 1989). However this training algorithm has not been successful for recurrent NN due to complexities (Blanco et al. 1990). Training algorithms for RNN, based on the error gradient, are very unstable in their search for a minimum and require much computational time when the number of neurons is high (Blanco et al.2000). This is the main reason where it is proposed a GA to evaluate weights.

The fitness function error is calculated as follow: Firstly, the weights in the network are set according to the weight vector; then the network is evaluated against the training sequence. It will lead to determinate the sum-squared-difference between training sequence and the known target values employed in the training sequence in each vector. The GA is adjusted to the weights, being the network represented by a chromosome and the weight link in summarised in one gene. There are many chromosomes that make up the population, therefore, many different neural networks are evolved until the minimum value of the mean-squared-error is satisfied. The fitness function evaluates the mean squared error in the training process for each NN, being the main objective to minimise the function.

Figure 1.

The system structure of a recurrent neural network

The output of the network can now be represented as:

$$Y(t)=f\left({\displaystyle \sum _{j=1}^N\left(f\left({\displaystyle \sum _{i=1}^{10}{U}_{ij}{X}_i(t)}\right)W_j\right)}\right)$$E12

$$X_{\text{10}}(t)=Y(t-1)$$E13

$$X_{10}(0)=0$$E14

where Y(t)= Output in iteration t. X_j(t)= Input i at iteration t. U_ij= Weights between input and the hidden layer. W_j= Weights between hidden layer and the output node. f = Activation function.

N is the number of neurons in the hidden layer.

The nomenclature followed is that U_ij connects jth node in input layer to ith node in hidden layer, similarly for W _j.

Let d be the desired output for k^th input, the error will be

$$Z_k\left(t\right)=\left|Y_k\left(t\right)-d_k\right|$$E15

The objective function for the GA is Z, which is the mean of square of errors for all values of inputs of X_j’s. Mathematically

$$Z(t)={\displaystyle \sum _{k=1}^n{Z}_k(t)*Z_k(t)/n}$$E16

The steps for GA employed are summarized in Figure 2.

The value of t is determined from the condition on mean square error (MSE) falling below a particular value

$$Z\left(t\right)\le \alpha$$E17

The method of obtaining the optimum values of the number of neurons in the hidden layer, and the Mutation and crossover fraction in the genetic algorithm parameters, is called parameter tuning, which is set by trials of different combination of the above parameters. The activation function used here is a sigmoid function given by:

$$f=\frac{1}{1+e^{-a(x-c)}}$$E18

a and c has been considered as 1, and the bias in the network has been made 0.

Pseudo Code
Setting up the neural network
		Set iteration counter t=0;
		Set Initial X n node = 0;
		Set Initial MSE=0.5;
Training of the network
While ( MSE "/> α )
		t=t+1;
Evaluate Z(t) in terms of training set of inputs and nodes ;
Call GA function with Z(t) as objective function
		Get A = solution given by GA ;
Evaluate Y(t) using A ;
Update node X n=Y(t);
End
Value of A from last iteration = A*
Testing of the network
Evaluate Z*(t) in terms of testing set of inputs, nodes and A*;
% Z*(t) is the final MSE and A* is the required weights of the networks %
Function Genetic Algorithm; Put initial value (Z(t)):
Put Size of initial population;
Choose crossover operator and mutation operator;
Put mutation ratio (M); Put crossover ratio (C); Put generation size;
End
For every generation do:
	For every chromosome do:
			Encode the chromosome;
			If chromosome feasibility= positive;
						Evaluate Z(t);
			Else; Back to encoding; End if
	Next: Compute chromosome ratio; Do
			Selection of specific gene population as obtained by chromosome ratio; Crossover; If chromosome feasibility= positive;
				Include it in initial population;
			Else
				Eliminate it;
			End if
	Iterate until crossover ratio (C) reached; Chromosomes sorted in increasing order as per Z(t) value: Select chromosomes keeping population size same as initial population size: Eliminate the left ones: Obtain chromosome ratio: Do
			Select 2 genes for mutation as per the chromosome ratio; Mutate; If chromosome feasibility= positive;
					Include it in the initial population;
			Else
					Remove it from database;
			End if
			Iterate until mutation ratio (M) is reached; Chromosomes sorted in increasing order as per Z(t) value:Select chromosomes keeping population size same as initial population size: Eliminate the left ones:
While decided number of iterations reached or values within specified error limit;

5. Results

The matrices of distances required in all algorithms are defines by the Table 2 for the principal route, Table 3 for the capillary route:

	Barcelona	Zaragoza	Madrid	Cuenca	Teruel	Lleida
Barcelona	0	290.6	606.5	486.5	367.5	151.8
Zaragoza	290.6	0	320.9	255.8	176.0	141.1
Madrid	606.5	320.9	0	164.4	293.9	460.8
Cuenca	486.5	255.8	164.4	0	129.8	368.9
Teruel	367.5	176.0	293.9	129.8	0	249.9
Lleida	151.8	141.1	460.8	368.9	249.9	0

Table 3.

Distance matrix. Madrid-Barcelona route

	Toledo	Bargas	Torrijos	Fuensalida	Recas	Illescas	Yuncos	Esquivias	Añover Tajo	Mocejón
Toledo	0	9.90	27.2	28.0	24.7	34.4	29.9	42.8	32.0	14.7
Bargas	9.90	0	24.4	24.5	15.1	26.5	22.0	34.8	26.9	10.6
Torrijos	27.22	24.4	0	10.8	37.8	50.4	45.6	58.9	51.4	35.1
Fuensalida	28.0	24.5	10.8	0	31.2	40.9	36.2	49.5	51.5	35.1
Recas	24.7	15.1	37.8	31.2	0	19.6	14.8	28.1	22.6	16.0
Illescas	34.4	26.5	50.4	40.9	19.6	0 0	4.80	8.50	19.5	25.6
Yuncos	29.9	22.0	45.6	36.2	8 8.14	4.80	0	13.4	15.0	21.1
Esquivias	42.8	34.8	58.9	49.5	28.1	8.50	13.4	0	21.9	34.0
Añover de Tajo	32.0	26.9	51.4	51.5	22.6	19.5	15.0	21.9	0	19.0
Mocejón	14.7	10.6	35.1	35.1	16.0	25.6	21.1	34.0	19.0	0

Table 4.

Distance matrix. Capillary Routes

REFERENCE SOLUTION	Route 1	Route 2	Capillary Route	Total
Total distance (km)	1223	114	209.9	1558.1
Number of Cities visited	2	2	1	5
Time	14h41	1h28	2h41	18h50
Fuel Cost (€)	366.93	34.22	31.49	432.64

Table 5.

Reference route provided by the company

RNNGA provides the following main route (see Figure 2):

Barcelona → Zaragoza → Madrid → Cuenca → Teruel → Lleida → Barcelona,

with a total distance of 1307.4 Km, only 84.4 km more than the reference route, but it presents better flexibility with two additional cities that are visited, employing 7 minutes more to cover the route than the reference route, with an extra cost of 20.19 €.

Figure 2.

Optimal solution for the principal route obtained by RNNGA

The capillary route found by RNNGA is (see Figure 3):

Toledo → Torrijos → Bargas → Fuensalida → Recas → Añover de Tajo → Illescas → Yuncos → Esquivias → Mocejón → Toledo

with a distance of 216.3 Km, 6.4 km more than reference route, with a fuel cost of € 32.51, reducing 4 minutes the reference route.

Figure 3.

Route capillary provides by RNNGA

The total distance and the cost of the main routes will be added the Madrid-Toledo trajectory (57 Km), covered in 44 minutes with a cost of 17.11 € (fuel). Table 5 shows the results of the routes found by RNNGA.

	RNNGA
Route1	Route2	Capillary route	Total
Total distance (km)	1307.4	114	216.3	1637.7
Number of cities visited	5	2	1	8
Duration	14h48	1h28	2h38	18h54
Fuel Cost (€)	346,74	34.22	32.51	413.47

Table 6.

Solution provided by the RNNGA.

6. Conclusions

A real case study has been considered, which the principal route consists in determining the route for sending a product set from Barcelona to Toledo (Spain). A first approach in this case study is to employ a route which passes through the maximum number of cities as possible minimizing costs, with the objective of maximise the flexibility. It will lead to the vehicle pick up or deliver products in those cities.

When the vehicle arrives from Madrid to Toledo (a direct route that will not be considered in the dual problem), the products require to be served in different towns close to Toledo. It is done following capillary routes. The case study considers a new vehicle that visits ten towns, starting and finishing in Toledo

The problem can be approximated to a series of problems similar to the vehicle routing problem with time windows (VRPTW). VRPTW tries to find a final solution including sub-path not connected and that meet the constraints of the travel salesman problem (TSP) considering the time windows constrains. The restrictions of Miller et al. (1960) have been used in order to reduce the computational cost. The main purposes of the method are to provide a quick solution and flexible enough to be used in a dynamic scheduling environment, and to develop a new solution procedure that is capable of exploiting the special characteristics of the problem.

This paper presents a meta-heuristic method that determines the routes that involve the major number of cities in order to increase flexibility, leading the vehicle deliver and pick up in these cities, trying to minimize the distance travelled and its costs.

A recurrent neural network approach is employed, which involves not just unsupervised learning to train neurons, but an integrated approach where Genetic Algorithm is utilized for training neurons so as to obtain a model with the least error.