Research Article
Genetic Algorithm Application for Multimodal Transportation Networks
School of Mechanical Engineering, Huaihai Institute of Technology, China
Xiaoli Wang
School of Mechanical Engineering, Huaihai Institute of Technology, China
Domestic and foreign scholars have done a series of studies about this problem. Based on the choice of transport modes and transport networks, a combinatorial optimization for much-model transport is get. On the principle of the minimization of cost, a multimode transportation network assignment model is presented. And rational organizational modal of multimodal transportation is analyzed in the study (Jian-Yong and Yao-Huang, 2002). Shortest path problem of multimodal transportation is studied on each directed edge corresponds to one mode of transport cases. Multimodal transport problem is converted to a specific shortest path problem with time and capability limitation by constructing a virtual transportation networks. An efficient heuristic algorithm to solve the specific shortest path is given in the study (De-Zhi and Chun-Yu, 2001). In the model, the up-level is time window model of goods and the lower-level is path optimization model (Wendong and Wenfang, 2009).
The time window constraints are not considered in most of these studies or the lower bound of time window constraints is not taken into account which is not very consistent with the actual. Based on the above analysis, a multimodal transport network model is established in this study and a genetic algorithm is designed to solve lower-level model (Lozano and Storchi, 2001).
PROBLEM DESCRIPTION
Suppose an express freight transportation company wants to deliver a shipment of goods from city (O) to city (D). In transport network there are several paths (Fig. 1). There are many kinds of transport modes with different costs and time between two cities.
Fig. 1: | Graph of transportation network |
And the goods must be delivered within the specified time window promised by the company. The objective is to find the best transport mode and route to make the total cost of transportation minimum.
MODELING
The problem can be converted to a single source and single sink network G = (V, E, C) (Fig. 1), V is the set of nodes and V = {O, P1,..., Pn, D}; E is the set of arcs, arcs set can be expressed at E = E1cE2cE3; where, E1 = {eopi|city Pi is adjacent to city O} and E2 = {eij|eages between intermediate city Pi and Pj}, E3 = {ePID|city Pi is adjacent to city D}; C is the weights set of the edges and represents unit transportation costs, the distance between the two cities and the average speed of vehicles, respectively. Therefore, the objectives are to find the least-cost shortest path with the constraint of time window from O to D.
Model assumptions:
• | Only one transportation mode can be chosen between two cities |
• | Transfer only happens in the city and just once |
• | Delay time is included in the transit time |
Symbol description: In order to describe the problem and model, the symbol of description are as follows:
• | Constant: m stands for the total tonnage of goods, n stands for the number of cities that vehicles go through, K stands for the set of transport mode, K = {1, 2,..., k}; dkij stands for transport distance between city i and j while choosing the kth transport mode, (i, j)εE, k = 1, 2,Y,K; wikl stands for transfer cost if goods transfer from transport mode k to transport mode l in city i; i = 1, 2,..., n, k = 1, 2,Y, K and k ≠ l; tkij stands for transport time between city i and city j while choosing the kth transport mode, (i, j)εE, k = 1, 2,..., K; ttikl; stands for transfer time if goods transfer from transport mode k to transport mode l in city i; i = 1, 2,..., K and k ≠ l; vkij stands for average transport speed between city i and city j while choosing the kth transport mode, (i, j)εE, k = 1, 2,Y, K |
• | Variable: xkij is 0-1 variable, from city i and city j, if choose the kth transport mode, then xkij = 1, otherwise xkij = 0, (i, j)εE, k = 1, 2,..., K; xkij is 0-1 variable, in city i, if goods transfer from transport mode k to transport mode l, then xikl = 1, otherwise xikl = 0, iε(l,..., n), k,l = 1, 2..., K and k ≠ l |
Bi-level programming model: For express freight transportation companies, distance and total time commitment are important indicators to measure quality of service. However, considering both of them at the same time is difficult to deal with in the model. So, this study presents a bi-level programming model, the up-level finds correspondence between services and time windows, the lower-level establishes an optimization model with minimum cost as the goal to determine the optimal path according to time window constraints (Wu et al., 2011).
Time window model: In the up-level model, the objective is to find a route from O to D with the minimum total distance:
(1) |
(2) |
(3) |
(4) |
Constraint 1-3 are the flow conservation constraints that form a path from node O to node D, while constraint 4 ensures that xkij are 0-1 variables.
If transportation service can be divided into L levels, each one corresponds to the time window constraint (tl-1, tl) l⊆L, get the shorts path through time window model and the relationship between time window and the transport distance is as follows:
(5) |
In the model, the scope of dl-1≤d≤dl, l = 1, 2,..., L is the restriction of service distance (Gentile et al., 2005).
Route optimization model: In the lower-level model, the objective is to find a route from O to D with the minimum total transport cost:
(6) |
(7) |
(8) |
(9) |
(10) |
(11) |
(12) |
Constraint 6 calculates transport time between city i and city j while choosing the kth transport mode; Constraint 7 is the time window constraints that specifies the scope of the arrival time that goods must get to the destination. Constraint 8-10 are the flow conservation constraints form a path from node O to D, while constraint 11 ensures that xkij and xikl are 0-1 variables (Niksirat et al., 2012).
SOLUTION BASED ON GENETIC ALGORITHM
The up-level model is a typical Shortest Path Problem (SPP) in graph theory and there are many algorithm to solve it. Such as Dijkstra algorithm, dynamic programming algorithm, A algoriyhm and so on (Tao and Guang, 2005). The lowest-level can be regarded as SPP with constraint of time window. The traditional algorithm is not flexible enough to solve such problems and when there are many nodes in the network, it will be an exponential growth in the computation. In this study, propose a new algorithm called genetic algorithm to solve it.
Chromosome encoding method: Chromosome encoding method has a great influence on the speed of solving the problem, the scope of solution and the size of error rate. In this study, adopt binary encoding method and chromosome length is the number of cities (Table 1).
Symbol Pi(i = O, 1, 2,..., n, D) is the number of city node. If the value of the node is 1, that means vehicles pass through the city; or if the value is 0, that means vehicles don=t pass through the city.
Fitness function: The problem of survive of any individual is determined by its fitness. The objective of this problem is using a route from O to D with the minimum estimated value Cmax.
Genetic operators: In the genetic algorithm, there are three main genetic operators, selection, crossover and mutation. By using different probabilities for applying these operators, the speed of convergence can be controlled. Crossover and mutation operators must be carefully designed, since their choice highly contributes to the performance of the whole genetic algorithm.
Selection operation: In this study, the genetic algorithm in this study uses an elitist selection based on the roulette wheel spin method and elitism strategy.
Crossover operation: The crossover operator mixes parts of two parent solutions to create two different offspring solutions. In this study crossover is carried out by the one-point method. And the crossover probability is 0.9.
Mutation operation: A new individual is created by making modifications to one selected individual. An integer mutation position along the chromosome is selected uniformly at random and then a chromosome to be mutated is randomly selected with a mutation probability.
Table 1: | Chromosome encoding method |
Table 2: | Transfer costs and time of different nodes |
Fig. 2: | Multimodel transportation network |
Simulated operation: Some inferior solutions are accepted by carrying out simulated operation and premature phenomenon can be effectively avoided.
Usually, the company wants to get a set of routes, so if the optimal route is damaged by some accidental factors, they can select other sub-optimal route to replace it. In this study, route can be got by special programming.
EXPERIMENT
Suppose an express freight transportation company wants to deliver a shipment of goods from city (O) to city (D). In transport network there are several paths. Demand of goods in city D is 100t and two transport modes including highway (defined as symbol) and railway can be chosen between two cities. The companys proposed pledges is that if distance is less than 400 km, goods can be delivered in 9 h; if distance is between 400 and 800 km, delivery time is 13-17 h; if distance is between 800 and 1600 km, delivery time is 25-32 h; if distance is between 1600 and 2400 km, delivery time is 38-43 h. goods distribution time is 5 h (Huacan et al., 2008). Some other useful data are listed.
Goods must be delivered within the specified time window promised by the company (Yang et al., 2010). The objective is to find the best transport mode and route from city (O) to city (D) to make the total cost of transport minimum (Fig. 2) and the results are Table 2-4.
According to the time window model, the shortest path route O→1→3→D can be got and the shortest distance is 580 km. Based on the correspondence between delivery time and transport distance, the time window constraints is 13-17 h.
Table 3: | Relevant parameters of different transport modes |
Table 4: | Minimum cost without considering the constraint of time window |
Table 5: | Minimum cost while considering the constraint of time window |
If the time window constraint is considered, some routes may be given up or some other measures should be taken to meet transport time constraint. The result is just as shown in Table 5.
EXPERIMENTAL RESULTS
From Table 3 and 4, the optimal route is given up, since it is limited by the time window. Meanwhile, note that its transport time is just beyond the time window 0.4 h but additional expenditure of 1600 yuan is needed. Therefore, the company should improve work efficiency and shorten distribution time or other measures to compares transport time in order to meet the constraint of time window.
The existing multimode combined transport static path optimization problem research, put forward the concept of combined transport reasonable path. Based on the combined transport process analysis of the reasonable path of the main meaning. By constructing a combined transport network diagram, this paper analyzes the total transportation cost and the composition of the total time, combined transport reasonable path choice problem is transformed into a sequence of reloading and reloading times of multiple constraints of the generalized cost the most short circuit problems and the corresponding mathematical model was established. Model can be combined transport operator in the transportation organization optimization decision provides the reference and at the same time, through the different solving method for comprehensive transportation network on the flow of multipath loading and transportation is consistent with practice to provide the reasonable path. Combined transport path way reasonable sequence is not static. Comprehensive transportation network users can only in the current technical condition under the restriction of the choice of mode of transportation of the best combination and travel path. The rationality of combined transport path of the connotation of the deepening of the research still needs some statistical data and data support, so that the models are reasonable correction, so as to provide more comprehensive transportation research beneficial reference value.