International Journal of Performability Engineering, 2019, 15(2): 464-474 doi: 10.23940/ijpe.19.02.p11.464474

Modeling of Spare Parts Supply Route Optimization with Hard Time Windows

Ming Han, Yabin Wang,, and Zhonghua Cheng

Department of Management Engineering,the Army of Engineering University of PLA, Shijiazhuang, 050003, China

Corresponding authors: E-mail address: wangyabin123@163.com

Received: 2018-12-12   Online: 2019-02-25

作者简介 About authors

Ming Han is a graduate student at Army Engineering University studying management science Her main research area is supply engineering .

Yabin Wang is an associate professor and postgraduate tutor at Army Engineering University His main research area is reliability , E-mail: wangyabin123@163.com.

Zhonghua Cheng is a professor and doctoral supervisor at Army Engineering University His main research area is managementengineering .

Abstract

In view of the spare parts supply route problem with hard time windows in transportation, an optimal model thataims to minimize the total delivery time is put forward. In this paper, the supply route optimization problem with the shortest transportation distance as the decision target is discussed in detail. Taking the shortest total transportation distance of all vehicles as the optimization goal, a mathematical analytical model thatconsiders the hard time window requirements of each customer is established. Based on the improved ant colony algorithm, the algorithm flow of solving the vehicle routing problem with hard time windows is designed to solve the difficulty of the model. In addition, the feasibility of the improved algorithm is verified by a case considering the actual terrain. The results show that the improved algorithm can quickly find the solution of VRPTW and provide an effective delivery plan for decision makers.

Keywords: spare parts supply; route optimization; modeling; hard time windows; ant colony algorithm

PDF (493KB) Metadata Metrics Related articles Export EndNote| Ris| Bibtex  Favorite

Cite this article

Ming Han. Modeling of Spare Parts Supply Route Optimization with Hard Time Windows. [J], 2019, 15(2): 464-474 doi:10.23940/ijpe.19.02.p11.464474

1. Introduction

The research on vehicle routing problem (VRP) beganin 1959. Based on the unremitting efforts of experts at home and abroad in this field, a series of intelligent algorithms have been introduced into the field of research, such as thetabu search algorithm, simulated annealing algorithm, ant colony algorithm, genetic algorithm, artificial neural network, and particle swarm optimization algorithm[1-9]. However, there are few articles on intelligent algorithms to explore the optimal decision-making problem of spare parts supply paths with time windows.

Spare parts are the premise and foundation for maintenance support. A timely and effective spare parts supply can provide a reliable guarantee of the smooth development of maintenance activities. The task-oriented spare parts supply and transportation require decision-makers to organize the transportation power reasonably, select the transportation route scientifically, deliver the spare parts of the customers on time and accurately, meet the customer’s spare parts time demands and quantity requirements properly, and achieve the maximum benefit perfectly. Generally speaking, scientific and reasonable transportation can not only reduce the cost of spare parts transportation, but also save capacity and improve the speed of spare parts turnover. There are many literatureson various supply problems. We need to select key points according to spare parts supply features and transportation characteristics. At present, the hot spot of theoretical research is the shortest path problem. It involves large-scale network nodes, while there are a few road network nodes between the transportation starting point and the transportation end. The transportation routes in the small range are even generally determined. Therefore, it is of great theoretical and practical significance to study the task-oriented optimization decision problem of the supply route. This paper uses an operational research method to establish a task-oriented optimization model of the spare parts supply routing problemand designs an intelligent solution algorithm to solve this model.

2. Analysis of Spare Parts Supply Route

2.1. Supply Route Problem

The supply route problem can be defined as a problem requiring the optimization of a set of transport routes for the flow of goods that can meet a series of constraints, in the background that a known transport vehicle from one or more warehouses to a multi geographically dispersed demand force. The purpose of VRP is to build a reasonable vehicle operation route and make the vehicle meet the minimum cost of transportation. The problem of task-oriented spare parts supply route optimization can be understood as a simple situation: there is only one spare parts warehouse, the transportation task is known, the vehicle starts from the spare parts warehouse, a transportation pathis chosen, and then it returns to the spare parts warehouse after the service of several spare parts. The output of the problem is to determine the number of transport vehicles needed and the transportation route of each vehicle. The requirement of the problem is to make the optimization decision of the spare parts supply route and achieve the maximum economic benefit, that is, to determine the required capacity (number of vehicles) and the transportation route of each car with a certain optimization goal and meet the requirements of the transportation task.

Therefore, the problems studied in this paper can be described in detail as the number of spare parts that are known to be shipped to each demand customer, and the spare parts warehouse can organize several transport vehicles of the same type to complete the transport task. Each vehicle has a capacity limit—the total amount of spare parts contained should not exceed its capacity. At the beginning, all the vehicles are in the warehouse, and our customers are distributed arbitrarily in the space. The number of vehiclesneeded and the route of each car must be determined, so that the spare parts can be transported to the customers in order. Finally, all the vehicles return to the spare parts warehouse.

The assumptions that need to be met are as follows:

· All transport vehicles start from the spare parts warehouse and eventually return to the spare parts warehouse;

· Every demand customer is only visited by a car once, and each vehicle can only serve one route;

· On every transport route, the sum of spare parts delivered to each customer cannot exceed the vehicle load.

2.2. Time Window Problem

Generally speaking, the arrival time of the spare parts is limited by the customer. Therefore, the vehicle routing problem has time constraints. This requires that the transportation process must be considered to meet the need first and then meet the general requirements. For further research, vehicle routing problems with time windows (VRPTW) are introduced here. Based on the traditional VRP, the VRPTW takes the time window constraint in consideration. The time window constraint can be divided into three types: hard time windows, soft time windows, and mixed time windows. The VRPTW problem includes three key problems: path finding, loading capacity restriction, and spare parts customer service order. The VRPTW must consider the demand of each customer for the time, so the determination of the customer service order is the key point that VRPTW should pay attention to[10-18].

In the process of spare parts transportation, the demand for spare parts delivery time is very high for each spare part. If the spare parts cannot be sent to the customer within the specified time, it will directly affect the economic benefit of the customer. Therefore, this paper focuses on the research of VRPTW.

2.3. Optimization of Target Selection

For the choice of optimization target, transportation time and distance are priority factors. The requirements of the hard time window for each customer will be considered during the modeling process. The transportation distance, transportation damage, transportation cost, and other factors are proportional to the transportation distance. Thus, shortening the transportation distance, both from the macroscopic angle and from the micro angle, is beneficial to the improvement of the transport efficiency of spare parts. As a result, the shortest transportation distance is used as the optimization target to meet the military benefit while the economic benefit is also taken into account, which is beneficial to the improvement of the comprehensive transport efficiency of spare parts. Therefore, the optimization objective is determined as follows: the shortest total distance of all vehicles.

3. Modeling of Spare Parts Supply Route Optimization

3.1. ModelHypothesis

Assume that for an existing transport task, the number of spare parts delivered to the demand customer $i$ is ${{q}_{i}}$, and the demand customer $i$ has a time window $[0,{{b}_{i}}]$, which means that the vehicle must reach the demand customer $i$ before the time ${{b}_{i}}$. In addition, the spare parts warehouse also has a time window $\left[ {{a}_{0}},{{b}_{0}} \right]$, which indicates that the vehicle cannot leave the spare parts warehouse before ${{a}_{0}}$ and must return to the spare parts warehouse before or before the ${{b}_{0}}$. For each requirement customer $i$ and the vehicle $k$ definition variable ${{t}_{ik}}$, it indicates that at time ${{t}_{ik}}$, vehicle $k$ accesses the demand customer $i$. If the vehicle $k$ does not access the demand customer $i$, then ${{t}_{ik}}$ does not have any meaning. Suppose ${{a}_{0}}=0$, so that for all vehicles $k$,${{t}_{0k}}=0$. Set the number of customers that ${{n}_{k}}$ serves for the vehicle $k$, using the set ${{R}_{k}}$ to express the path passed by the vehicle $k$. The element ${{r}_{ik}}$ indicates that the order of the customer ${{r}_{ik}}$ in the path $k$ is $i$ (excluding the spare parts warehouse).

3.2. Symbolic Description

To facilitate the description of the problem, the commonly used symbols in the model are as follows:

· The number of vehicles needed is $V$, the loading capacity of each vehicle is $Q$, the number of spare parts for customer $i~$is$~{{q}_{i}}$, and ${{q}_{i}}<Q$;

· The demand customer set is $C$;

· The definition of a directed graph is $G$, the directed graph has $n+2$ vertices, the vertex $1,2,\cdots ,n$ represents spare parts demand customers, vertex $0$ indicates the spare parts warehouse when the vehicle leaves, and virtual $n+1$ represents the spare parts warehouse when the vehicle returns;

· The vertex $0,1,2,\cdots ,n+1$ is recorded as a set of $N$, and the collection of arcs among demand customers and between demand customers and spare parts warehouses is recorded as $A$. No arc begins at the vertex $n+1$ and no arc terminates at the vertex $0$;

· The distance between each $arc(i,j)$ corresponds to ${{d}_{ij}}$, its corresponding transport time is ${{t}_{ij}}$, and the corresponding quantity of transportation is${{q}_{ij}}$.

3.3. Mathematical Model Construction

For each $arc~\left( i,j \right)$, $\left( i\ne j,i\ne n+1,j\ne 0 \right)$ and vehicle $k$,define the variable ${{x}_{ijk}}$ as

${{x}_{ijk}}=\left\{ \begin{matrix} 0, & \text{If the vehicle} k \text{does not reach the node} j \text{from the node} i \\ 1, & \text{If the vehicle} k \text{does reach the node} j \text{from the node }i \\\end{matrix} \right.$

It is necessary to design a path with the minimum total transportation distance for all vehicles. This path should begin at the vertex $0$ and terminate at the vertex $n+1$. It ensures that the spare parts for each customer’s demand is satisfied. The hard time windows of the customers and the traffic constraints of the vehicles are not violated. By describing the above parameters, the mathematical model of VRPTW can be expressed as

$\min \sum\limits_{k=1}^{k}{\left[ \sum\limits_{i=1}^{{{n}_{k}}}{{{d}_{{{r}_{k(i-1)}}}}_{{{r}_{ki}}}+{{d}_{{{r}_{k{{n}_{k}}}}{{r}_{k({{n}_{k}}+1)}}}}\times sign({{n}_{k}}-1)} \right]}$

S.t.

$0\le {{n}_{k}}\le n$
$\underset{i=1}{\overset{{{n}_{k}}}{\mathop \sum }}\,{{q}_{{{k}_{i}}}}\le Q,\text{ }\forall k\in V$
${{R}_{k}}\text{=}\left\{ {{r}_{ki}}|{{r}_{ki}}\in \left\{ 1,2,\cdots ,\left. n \right\} \right.,\text{ }i=1,2,\cdots ,{{n}_{k}} \right\}$
$\underset{j\in N}{\mathop \sum }\,{{x}_{ojk}}=1,\text{ }\forall k\in V$
$\underset{i\in N}{\mathop \sum }\,{{x}_{ihk}}-\underset{j\in N}{\mathop \sum }\,{{x}_{hjk}}=0,\text{ }\forall k\in V,\text{ }\forall h\in C$
$\underset{i\in N}{\mathop \sum }\,{{x}_{i\left( n+1 \right)k}}=1,\text{ }\forall k\in V$
${{t}_{ik}}\le {{b}_{i}},\text{ }\forall k\in V$ (9)
${{x}_{ijk}}\in \left\{ 0,\left. 1 \right\} \right.,\text{ }\forall k\in V,\text{ }\forall i,j\in N$(10)
${{q}_{i}},{{b}_{i}},{{d}_{ij}},{{q}_{ij}},{{t}_{ij}}\in {{Z}^{+}},\text{ }\forall i,j\in N$
$sign\left( {{n}_{k}}-1 \right)=\left\{ \begin{array}{*{35}{l}} 1,\text{ }{{n}_{k}}\ge 1 \\ 0,\text{ otherswise} \\\end{array} \right.$

Equation (2) indicates that the total distance of transportation targets for all vehicles is the shortest.

Equation (3) represents that the number of customers of every path service is not more than the total number of customers. Among them, ${{n}_{k}}$ is the demand customer number of service on route $k$, and $n$ indicates the total number of customers.

Equation (4) indicates that the total amount of spare parts transported to each customer on each path is no more than the capacity limit of the vehicle.

Equation (5) represents the path composition of the $k$ vehicle.

Equations (6)-(8) indicate that each vehicle starts at the spare parts warehouse and finally returns to the spare parts warehouse after visiting the demand customer.

Equation (9) indicates that the vehicle must meet the time window requirements of the visiting customers during the driving process.

Equations (10)-(11) are value constraints.

4. Optimization Model Solution

The vehicle routing problem with hard time windows has been proven to be a NP difficult problem. At present, there are many algorithms to solve such problems. For large vehicle routing problems, there are genetic algorithms, greedy algorithms, tabu search algorithms, simulated annealing algorithms, and so on. In this paper, a model solving method based on the ant colony algorithm is designed, which makes the model feasible for large vehicle routing problems.

4.1. Parameter Setting

$m$:The number of ants in the ant colony;

$\alpha $: The information elicitation factor indicates the relative importance of pheromones;

$\text{ }\!\!\beta\!\!\text{ }$: The expected elicitation factor indicates the relative importance of visibility;

$\text{ }\!\!\rho\!\!\text{ }$: A coefficient that represents the attenuation of the amount of information within the time interval $(t,t+n)$, besides$0\le \text{ }\!\!\rho\!\!\text{ }\le 1$;

${{\tau }_{ij}}$: The intensity of the pheromone on the edge $e\left( {{v}_{i}},{{v}_{j}} \right)$;

${{\eta }_{ij}}$: The visibility of edge $e\left( {{v}_{i}},{{v}_{j}} \right)$, reflecting the degree of inspiration of the choice edge $e\left( {{v}_{i}},{{v}_{j}} \right)$. Generally there is ${{\eta }_{ij}}=1/Di{{s}_{ij}}$;

$P_{ij}^{k}$: The probability of an ant$k$being transferred to ${{v}_{i}}$ from a node $k$;

$\Delta {{\tau }_{ij}}$: The pheromone increment of the unit length of the ant k on the edge $e\left( {{v}_{i}},{{v}_{j}} \right)$;

$Di{{s}_{ij}}$: The distance from node ${{v}_{i}}$to node ${{v}_{j}}$ onthe side of connection ${{v}_{i}},{{v}_{j}}\in V.$

4.2. Algorithm Solving Process

In the ant colony system, ants have the following characteristics: (1) Choose the transfer route by probability, and the probability is the function of the distance between nodes and the amount of information on the path; (2) After the completion of a cycle, a certain amount of pheromone is left on the path it has passed; (3) The pheromone of ants on the path gradually undergoes volatilization (attenuation). In the initial time, the pheromone amount on each path is equal. Ants in the ant colony system randomly select the transfer path and leave the pheromone of the path information on the path through which it passes. Later, the ants then choose the path according to the distribution of pheromones and the visibility of the feasible paths, making the better path pheromone increase. After a period of adjustment, all the ants tend to move along a path, which finds the optimal or approximate optimal path.

The general flow chart of solving the ant colony algorithm is given in this paper, as shown in Figure 1:

Figure1.

Figure 1.   The generalflow of antcolonyalgorithm


· Initialization:Set the initial value of the parameter: the pheromone given at the initial time ${{\tau }_{ij}}\left( 0 \right)=c$; pheromone increment $\Delta \tau \left( 0 \right)=c$; visibility weight factor ${{\eta }_{ij}}$. It is usually obtained by some heuristic algorithm, take ${{\eta }_{ij}}=1/Di{{s}_{ij}}$.

· Release the ant colony:The initial node is randomly given to record the starting point of ants, which is used as a symbol to decide whether ants search all paths.

· Choose the direction of movement according to probability: In every optimization process, ants choose the next node according to probability. The probability of ant selection node ${{v}_{i}}$ on node ${{v}_{j}}$ is determined by pheromone concentration ${{\tau }_{ij}}$ and visibility factor ${{\eta }_{ij}}$.

The transfer probability is expressed as

$P_{ij}^{k}\left( t \right)=\left\{ \begin{matrix} \frac{\tau _{ij}^{\alpha }\left( t \right)\eta _{ij}^{\beta }\left( t \right)}{\mathop{\sum }_{s\in allowe{{d}_{k}}}\tau _{iS}^{\alpha }\left( t \right)\eta _{iS}^{\beta }\left( t \right)}, & j\in allowe{{d}_{k}} \\ 0, & \text{otherwise} \\\end{matrix} \right.$

Among them, $allowe{{d}_{k}}=\left\{ V-tab{{u}_{k}} \right\}$ is the node that ants $k$ can choose in the next step, that is, the point connected with the current node, $V$ is the set of target nodes that ants can choose, $tab{{u}_{k}}$ represents the set of paths that the ant has passed by $k$, and the relative importance of the pheromone intensity information and the visibility information, respectively, by$\alpha $ and $\beta $ as two parameters, is generally determined by the experiment.

· Update the pheromone:Once a cycle is completed, the pheromone quantity on the obtained path is adjusted according to the following formulas:

${{\tau }_{ij}}\left( t+1 \right)=\left( 1-\rho \right){{\tau }_{ij}}\left( t \right)+\text{ }\!\!\Delta\!\!\text{ }{{\tau }_{ij}}\left( t,t+1 \right)$
$\Delta {{t}_{ij}}\left( t,t+1 \right)=\sum\nolimits_{k=1}^{n}{\Delta \tau _{ij}^{k}\left( t,t+1 \right)}$

Among them,$\Delta \tau _{ij}^{k}\left( t,t+1 \right)$ indicates that at the $\left( t,t+1 \right)$ time, $k$ ants remain on the pheromone on the side$e\left( {{v}_{i}},{{v}_{j}} \right)$,$\rho $is the attenuation coefficient of the pheromone, and$\text{ }\!\!\Delta\!\!\text{ }\tau _{ij}^{~}\left( t,t+1 \right)$ represents the increment of the pheromone on the $e\left( {{v}_{i}},{{v}_{j}} \right)$ sides of this cycle.

4.3. Improvement of Solving Algorithm

4.3.1. Dynamic Adjustment of Feasible Point Set Allowedk

In the VRPTW problem, every ant needs to traverse all road network nodes. Therefore, in each iteration of the VRPTW problem, the number of movements of each ant is uncertain and can only be returned to the starting point (warehouse) as a sign to be constructed as a path. The tabu list $tab{{u}_{k}}$ of the walking network set contains two identical origin nodes.

In solving the VRPTW problem based on the ant colony algorithm, the path construction process is divided into two stages:

· If the initial location of an ant is not a spare parts warehouse, the first stage is the process of looking for the spare parts warehouse from the initial node, called “process I”. In this process, the feasible point set $allowe{{d}_{k}}$ should include the spare parts warehouse instead of the initial node. After arriving at the spare parts warehouse, the next step is to start from the spare parts warehouse and look for a path to return to the initial node, which is called “process II”. In this process, the spare parts repository cannot be contained in $allowe{{d}_{k}}$ but should contain initial nodes.

· If the initial location of the ant is a spare parts warehouse, “process I” is the first move of the ant, that is, the process of moving the spare parts warehouse to any other node. Process II is the process of ants returning to the spare parts warehouse. Therefore, in process I, $allowe{{d}_{k}}$ cannot contain the spare parts warehouse, and in process II, the spare parts repository must be included.

To sum up, in order to meet the needs of path search, the feasible point set $allowe{{d}_{k}}$ needs to be dynamically adjusted.

4.3.2. Selection Probability Optimization

When ants choose the next spare part and demand customers, they should consider the premise of satisfying vehicle capacity and time window constraint. To the next spare part, we need the path length and the amount of information on the path. The choice and optimality of the time window factor is influenced by the time window of the next spare part demand $j$ and the time of the current node to the demand customer $j$, and then the priority principle of the timing window factor optimality is the shorter waiting time priority and the smaller time window. Therefore, in the current node$i$, this paper improves the calculation formula of the state transition probability of the next spare part demand customer $j$ on the path $k$ to

$P_{ij}^{k}\left( t \right)=\left\{ \begin{matrix} \frac{a\times \tau _{ij}^{\alpha }\left( t \right)\eta _{ij}^{\beta }\left( t \right)}{\mathop{\sum }_{s\in allowe{{d}_{k}}}\tau _{is}^{\alpha }\left( t \right)\eta _{is}^{\beta }\left( t \right)}+\frac{b\times \frac{1}{{{t}_{ik}}+{{t}_{ij}}}}{\mathop{\sum }_{S\in allowe{{d}_{k}}}\frac{1}{{{t}_{ik}}+{{t}_{ij}}}}, & j\in allowe{{d}_{k}} \\ 0, & \text{otherwise} \\\end{matrix} \right.$

Among them, $a$ and $b$ are weight coefficients,$a+b=1$, and $allowe{{d}_{k}}=\left\{ V-tab{{u}_{k}} \right\}$.

4.3.3. Parameters Optimization

In order to reduce search stagnation, we limit the pheromone to interval $\left[ {{\tau }_{\min }},{{\tau }_{\max }} \right]$. In this way, the pheromone concentration on a path will not be much larger than other paths, and the algorithm will no longer diffuse.

In the initial stage of ant colony optimization, a larger $\rho$ value can help ants choose paths. From the research results of document [19], it is known that when the pheromone volatilization factor $\rho$ is $0.5$, the overall performance of the algorithm is better. Therefore, in the path optimization process, when the optimal solution obtained by the ant colony algorithm has no obvious improvement in the cycle process, it should be adjusted according to the following formula:

$\rho \left( t+1 \right)=\left\{ \begin{matrix} 0.95, & \rho \left( t \right)\ge 0 \\ 0.5, & \rho \left( t \right)<0 \\\end{matrix} \right.$

4.4. Algorithm Flow Design

Based on the improved ant colony algorithm, the algorithm flow of vehicle routing problem with hard time windows is designed in this paper. We can use the process of artificial ants accessing points to simulate the process of spare parts transportation vehicle service needs of customers. When the next spare part needs the customer to make the total amount exceed the number of existing spare parts, it returns to the spare parts warehouse, indicating that the car has completed the transportation. The car then starts to serve other spare parts and demand customers until all customers receive service. At this time, the artificial ants representing the vehicle have completed a cruise. When all the ants have completed a cruise, they write a cycle. Then, the number of vehicles needed is the number of ants who go all the way to the spare parts warehouse in the cycle. After a cycle, according to the advantages and disadvantages of each ant’s cruise, we calculate the increment of pheromones and update pheromones. After many cycles, most ants will choose the same path or find an approximate optimal path solution, and then solve it.

The concrete solution steps are as follows:

Step1 initialize system parameters, initial time $t=0$, iteration number $NC\_max=0$, read road network information, place m ants on the nodes representing the spare parts warehouse, set up an ant colony taboo table $tab{{u}_{k}}$ and feasible point set $allowe{{d}_{k}}$.

Step2 for each ant $i$, find the nodes that have not gone through the list of nodes, calculate the transfer probability according to the probability transfer Equation (16), and then use the roulette method[10] to select the customer $j$ for the next service of the ant.

Step3 after considering the spare parts supply of the customer $j$ of the path $(i,j)$, the total supply is $q$.If $q~<~Q$, jump to Step4, otherwise the node $j$ is added to the feasible point set $allowe{{d}_{k}}$ and jumps to Step5.

Step4 calculate the time to reach the demand customer $j$. If the time window is not satisfied, the node $j$is added to the tabu table $tab{{u}_{k}}$ to jump to Step2; otherwise, the node $j$ is rejoined in the feasible point set $allowe{{d}_{k}}$ and jumps to Step5.

Step5 ants return to the spare parts warehouse, and the number of vehicles increases by 1 (initial 0). Then, judge the feasible point set $allowe{{d}_{k}}$;if $allowe{{d}_{k}}$ is empty, jump to Step6; otherwise, get the unsearched nodes from $allowe{{d}_{k}}$, select the shortest node as the starting point, jump to Step2, and search the next node.

Step6 ants will update pheromone updates according to pheromone update Equations (14) and (15) after completing a cruise each time. Record the path and total length of each cruise.

Step7 when an ant completes the search, it searches for the shortest path length of the vehicle and the number of vehicles required in this iteration (the number of ant round-trip warehouses for the shortest path iteration of the shortest path). The optimal solution of this iteration is compared with the global optimal solution. If the optimal solution is superior to the global optimal solution, then the global optimal solution is replaced, and the pheromone is updated according to the pheromone updating Equations (14) and (15).

Step8 if the number of iterations reaches the maximum number of iterations or the global optimal solution is found, the optimal path solution and the number of vehicles will be output at the end of the program. Otherwise, clear tabu table, jump to Step2,and repeat the above steps.

It is necessary to explain that if the next service node is searched only according to the concentration of pheromone, the intelligent algorithm can easily converge to a path earlier. It cannot search for a shorter path in the space, that is, the phenomenon of stagnation occurs. In order to avoid premature convergence, Step2 used roulette to select the next node.

4.5. A Numerical Example

The warehouse command center collects the customer’s geographic location, customer order data, and the customer’s time window requirements.Based on the above data,the center draws a list of X spare parts supply tasks in the A area of April 23, 2018, as shown in Table 1.The warehouse A coordinates are (1.7km, 178km, 6.4m), which is responsible for the supply of X spare parts of 39 customers in the supply task list. Its transport vehicles are all type M vehicles. The load of a single transport vehicle is 170 X spare parts. As the area is close to the high speed, the road conditions and the rest time of the transporter are integrated, the average transportation time is 67km/h, and each car is equipped with two professional drivers. At 20:00 on April 22, 2018, the spare parts warehouseA finished loading 161 X spare parts according to the supply task list.According to the characteristics of the warehouse business and customer needs, the carrier with X spare parts must start from warehouse A at 8:00 on April 23, 2018 and then deliver the X spare parts in the hard time window specified by the customer. According to the company’s regulations, vehicles will return to warehouse A before 17:30 on April 23, 2018.

Table 1.   Order form of X in spare parts warehouse

No.CSRCoordinate
(km,km,m)
DemandDeadlineNo.CSRCoordinate
(km,km,m)
DemandDeadline
1FP(5.6,10.2,6.4)79:0021RN(7.7,10.6,6.8)58:50
2FQ(3.7,7.8,6.4)59:1022RJ(15.6,10.8,7.9)310:45
3FG(12.8,10.8,7.2)210:3023RS(19.9,9.9,7.7)210:55
4FM(13.1,12.9,7.1)410:3524AX(26.2,16.2,8.9)711:25
5TX(10.9,8.7,7.1)210:0525AN(32.1,17.6,8.1)611:35
6TY(9.7,5.6,6.9)39:4026AJ(7.8,31.2,8.1)416:40
7TG(36.5,19.8,9.2)211:4527AD(7.9,40.1,8.6)316:10
8TF(49.8,37.9,11.1)514:3528AT(4.6,16.7,6.2)510:00
9BG(70..2,68.9,6.4)213:5029AR(23.1,9.8,6.7)511:05
10BT(50.6,37.5,10.5)314:3030AZ(74.5,27.8,7.3)412:50
11BM(26.5,11.6,10.3)311:1531AX(42.1,42.5,9.9)814:45
12BA(10.8,11.3,8.9)510:2032XK(3.7,36.9,86)516:30
13JD(7.6,43.7,6.5)316:2033XJ(4.6,16.7,6.2)38:30
14JR(27.8,22.8,9.3)915:2534XC(5.9,17.8,6.5)28:40
15JX(32.1,22.1,9..5)215:1535XX(17.3,17.8,8.3)415:40
16ZW(11.3,10.9,7.6)310:1536XN(61.8,17.3,7.7)212:30
17ZM(81.2,24.5,8.8)713:0037XB(37.8,15.7,75)311:55
18ZB(46.2,6.1,6.9)412:1038XF(9.8,7.9,6.3)59:55
19ZT(43.9,27.8,7.2)415:0039XD(7.5,1.8,5.9)49:30
20RY(7.5,29.6,6.8)616:45Sum161

New window| CSV


We can use this improved algorithm to help the warehouse plan the shortest transportation path under the time window constraint. According to the 3D coordinates and related terrain information drawing in the order list, the topographic map of the distributed area is drawn by MATLAB to determine the undulation and passing of the road,as shown in Figure 2. The actual distance between nodes can be calculated more accurately through this way.

Figure2.

Figure 2.   The topographic map of the distribution area


Through the distribution of regional topographic maps, we find that the area of the 39 customers is a flat terrain, the road has a very small range of fluctuation, and good performance is achieved. Therefore, we can approximate the distribution distance between the distribution nodes in order by the three-dimensional space distance between point $i$ and point $j$.

Using the algorithmabove, the paper takes themaximum iterative algebra $NC\_\max =200$, the number of ants m=18, the information heuristic factor $\alpha $=1, the expected heuristic factor $\beta $=5, the information attenuation coefficient $\rho $=0.5, the probability weight $a$=0.6, and the probability weight $b$=0.4.

Through MATLAB operation, the output of this VRPTW problem is as follows:

· Number of vehicles used =1;

· The total length of the shortest path=324.4637km;

· The shortest route to visit the customers in order is

$\begin{matrix} & spare\text{ }part\text{ }warehouseA(start)\to XJ\to XC\to RN\to FP\to FQ\to XD\to TY\to XF\to AT\to TX\to ZW\to BA\to FG \\ & \to FM\to RJ\to RS\to AR\to BM\to AX\to AN\to TG\to XB\to ZB\to XN\to AZ\to ZM\to BG\to BT\to TF\to AX \\ & \to ZT\to JX\to JR\to XX\to AD\to JD\to XK\to AJ\to RY\to spare\text{ }part\text{ }warehouseA(destination) \\ \end{matrix}$

In other words, the result of fast solving the distribution problem by using the improved ant colony algorithm in this paper is: one car loading 161 spare parts should start from the spare parts warehouse A,pass XJ, XN, RN, FP, FQ, XD, TY, XF,and AT in order and finally returnto the spare parts warehouse A. This can satisfy all customers’ time window requirements and the company’s inherent working time limit. The shortest path for calculation is 324.4637 kilometers, as shown in Figure 3.

Figure 3.

Figure 3.   (a) Access order in the shortest path case;(b) The relationship between NC, mean distance, and shortest distance


5. Conclusions

This paper focuses on the task oriented spare parts supply routing optimization decision-making problem, and its research results can be directly used for vehicle routing optimization decisions in wartime spare parts. Considering the time window requirements of the company’s working time limit and each customer’s spare parts demand, a mathematical optimization model is established for the shortest distance of all vehicles with the total distance of distribution. From the scale of the problem, it belongs to the small problem category, which can obtain the exact solution of the model solution, but it can further expand the model of this chapter. Based on the characteristics of the model, the traditional ant colony algorithm is improved to solve the model. The optimization result is the output vehicle number, the transportation route, and the total distance of each vehicle. At the same time, a VRPTW case considering terrain is used to prove the effectiveness of the improved genetic algorithm in solving the VRPTW problem.

Acknowledgments

The authors are appreciative of the useful programming guidance given by Mr.Yu, who majored in precision guidance and simulation technology precision guidance and simulation technology at the Army of Engineering University of PLA University.

Reference

J. Brito, A. Expósito, J.A.M. Pérez,

“Bi-Objective Discrete PSO for Service-Oriented VRPTW,”

Advances in Evolutionary and Deterministic Methods for Design,Vol. 36,pp. 445-460,2015

DOI:10.1007/978-3-319-11541-2_29      URL     [Cited within: 1]

In this paper we deal with a variant of the VRPTW that is oriented to the quality of service to customers. In this model, we incorporate a measure of quality associated with the time the vehicles reach customers within their time window as an objective. We apply a bi-objective discrete PSO to deal with the problem. The procedure performance is analyzed on classical and real data based instances.

B. Ge, J. H.Han, Z. Wei, L. Cheng, Y. Han,

“Dynamic Hybrid Ant Colony Optimization Algorithm for Vehicle Routing Problem with Time Windows,”

Pattern Recognition and Artificial Intelligence,Vol.28,No.7,pp.641-650,July 2015

DOI:10.16451/j.cnki.issn1003-6059.201507008      URL    

To solve the vehicle routing problem with time windows( VRPTW),a dynamic hybrid ant colony optimization algorithm( DHACO) is proposed,so as to avoid the disadvantages of traditional ant genetic hybrid algorithm,such as static setting,redundant iteration and slow convergence. Firstly,an initial solution is obtained through max-min ant system,and the ant colony optimization algorithm is adopted to get a basic feasible solution to VRPTW. Then,the crossing and mutation operations of genetic algorithm are employed to re-optimize local and global solutions,thus the optimal solution is obtained. Finally,based on the fusion strategy of ant genetic hybrid algorithm,and by employing ant algorithm and genetic algorithm dynamically and alternately,the parameters of ant colony algorithm is self-adaptively controlled according to cloud association rules. DHACO reduces the times of redundant iteration and speeds up the rate of the convergence. Simulation results show that DHACO is better than the other related heuristic algorithms as to the optimal solutions.

Y. M. Guo, D. W. Hu, X. Chen,

“Solution of Emergency Logistics Open-Loop Vehicle Routing Problem with Time Windows based on Improved Ant Colony Algorithm,”

Journal of Changan University (Natural Science Edition), Vol. 37, No. 6, pp.105-112, November 2017

K. Ilker, E. Seval, A. Asli, O. Nursel,

“A Memory Structure Adapted Simulated Annealing Algorithm for a Green Vehicle Routing Problem,”

Environmental Science and Pollution Research, Vol. 22, No. 5,2015

DOI:10.1007/s11356-014-3253-5      URL     PMID:25056743     

Currently, reduction of carbon dioxide (CO 2 ) emissions and fuel consumption has become a critical environmental problem and has attracted the attention of both academia and the industrial sector. Government regulations and customer demands are making environmental responsibility an increasingly important factor in overall supply chain operations. Within these operations, transportation has the most hazardous effects on the environment, i.e., CO 2 emissions, fuel consumption, noise and toxic effects on the ecosystem. This study aims to construct vehicle routes with time windows that minimize the total fuel consumption and CO 2 emissions. The green vehicle routing problem with time windows (G-VRPTW) is formulated using a mixed integer linear programming model. A memory structure adapted simulated annealing (MSA-SA) meta-heuristic algorithm is constructed due to the high complexity of the proposed problem and long solution times for practical applications. The proposed models are integrated with a fuel consumption and CO 2 emissions calculation algorithm that considers the vehicle technical specifications, vehicle load, and transportation distance in a green supply chain environment. The proposed models are validated using well-known instances with different numbers of customers. The computational results indicate that the MSA-SA heuristic is capable of obtaining good G-VRPTW solutions within a reasonable amount of time by providing reductions in fuel consumption and CO 2 emissions.

K. N.Androutsopoulos and K. G. Zografos ,

“An Integrated Modelling Approach for the Bicriterion Vehicle Routing and Scheduling Problem with Environmental Considerations,”

Transportation Research Part C: Emerging Technologies, Vol. 82, pp.180-209, 2017

DOI:10.1016/j.trc.2017.06.013      URL    

The consideration of pollution in routing decisions gives rise to a new routing framework where measures of the environmental implications are traded off with business performance measures. To address this type of routing decisions, we formulate and solve a bi-objective time, load and path-dependent vehicle routing problem with time windows (BTL-VRPTW). The proposed formulation incorporates a travel time model representing realistically time varying traffic conditions. A key feature of the problem under consideration is the need to address simultaneously routing and path finding decisions. To cope with the computational burden arising from this property of the problem we propose a network reduction approach. Computational tests on the effect of the network reduction approach on determining non-dominated solutions are reported. A generic solution framework is proposed to address the BTL-VRPTW. The proposed framework combines any technique that creates capacity-feasible routes with a routing and scheduling method that aims to convert the identified routes to problem solutions. We show that transforming a set of routes to BTL-VRPTW solutions is equivalent to solving a bi-objective time dependent shortest path problem on a specially structured graph. We propose a backward label setting technique to solve the emerging problem that takes advantage of the special structure of the graph. The proposed generic solution framework is implemented by integrating the routing and scheduling method into an Ant Colony System algorithm. The accuracy of the proposed algorithm was assessed on the basis of its capability to determine minimum travel time and fuel consumption solutions. Although the computational results are encouraging, there is ample room for future research in algorithmic advances on addressing the proposed problem.

P. V.Silvestrin and M. Ritt ,

“An Iterated Tabu Search for the Multi-Compartment Vehicle Routing Problem,”

Computers and Operations Research, Vol. 81, pp.192-202, 2017

DOI:10.1016/j.cor.2016.12.023      URL    

We study a variant of the vehicle routing problem that allows vehicles with multiple compartments. The need for multiple compartments frequently arises in practical applications when there are several products of different quality or type, that must be kept or handled separately. The resulting problem is called the multi-compartment vehicle routing problem (MCVRP). We propose a tabu search heuristic and embed it into a iterated local search to solve the MCVRP. In several experiments we analyze the performance of the iterated tabu search and compare it to results from the literature. We find that it consistently produces solutions that are better than existing heuristic algorithms.

A. Utamima, K. R. Pradina, N. S. Dini, H. Studiawan,

“Distribution Route Optimization of Gallon Water using Genetic Algorithm and Tabu Search,”

Procedia Computer Science, Vol. 72, pp.503-510, 2015

DOI:10.1016/j.procs.2015.12.132      URL    

Distributions of drinking water in gallons often do not pay attention to the problem of finding the most optimal route, thus causing inefficiency in the cost of shipping. To minimize incurred costs, it is necessary to minimize vehicle fleet and amount of travel distance, with the restriction that the vehicle must have sufficient capacity to transport the goods to be shipped and return it back to the depots. This problem could be framed as a Vehicle Routing Problem with pick-up and delivery (VRPPD). In this paper, we propose a method to optimize delivery route in a drinking water depot by combining genetic algorithm (GA) and Tabu search. GA has advantages by providing possible solutions while Tabu covers up its shortfall in identifying local solutions so that searching will able to avoid loop in the area of the same solution. Experimental results show that the proposed method is more efficient than a manually predetermined route.

T.Y. Wu, J. H. Xu, J. Y. Liu, L. Zan,

“Improved Genetic Algorithm for Vehicle Routing Problem with Hard Time Window,”

Systems Engineering and Electronics, Vol. 36, No. 4, pp.708-713, April 2014

H. Yousefi, R. T. Moghaddam, M. T. BOliaei,M. Mohammadi, and A. Mozaffari,

“Solving a Bi-Objective Vehicle Routing Problem under Uncertainty by a Revised Multi-Choice Goal Programming Approach,”

International Journal of Industrial Engineering Computation, Vol. 8, No. 3, pp.283-302, 2017

[Cited within: 1]

A. Alvarez and P. Munari,

“An Exact Hybrid Method for the Vehicle Routing Problem with Time Windows and Multiple Deliverymen,”

Computers and Operations Research, Vol. 83, pp.1-12, 2017

DOI:10.1016/j.cor.2017.02.001      URL     [Cited within: 2]

The vehicle routing problem with time windows and multiple deliverymen (VRPTWMD) is a variant of the vehicle routing problem with time windows in which service times at customers depend on the number of deliverymen assigned to the route that serves them. In particular, a larger number of deliverymen in a route leads to shorter service times. Hence, in addition to the usual routing and scheduling decisions, the crew size for each route is also an endogenous decision. This problem is commonly faced by companies that deliver goods to customers located in busy urban areas, a situation that requires nearby customers to be grouped in advance so that the deliverymen can serve all customers in a group during one vehicle stop. Consequently, service times can be relatively long compared to travel times, which complicates serving all scheduled customers during regular work hours. In this paper, we propose a hybrid method for the VRPTWMD, combining a branch-price-and-cut (BPC) algorithm with two metaheuristic approaches. We present a wide variety of computational results showing that the proposed hybrid approach outperforms the BPC algorithm used as standalone method in terms of both solution quality and running time, in some classes of problem instances from the literature. These results indicate the advantages of using specific algorithms to generate good feasible solutions within an exact method.

J. C. Paz, M. G. Echeverri, J. W. Escobar,

“The Multi-Depot Electric Vehicle Location Routing Problem with Time Windows”

, International Journal of Industrial Engineering Computations, Vol. 9, No. 1, pp.123-136, 2018

F. Errico, G. Desaulniers, M. Gendreau, W. Rei, L.M. Rousseau,

“A Priori Optimization with Recourse for the Vehicle Routing Problem with Hard Time Windows and Stochastic Service Times”

, European Journal of Operational Research, Vol. 249, No. 1, pp.55-66, 2016

DOI:10.1016/j.ejor.2015.07.027     

The VRPTW-ST introduced by Errico et al. (2013) in the form of a chance-constrained model mainly differs from other vehicle routing problems with stochastic times considered in literature for the presence of hardtime windows. This makes the problem extremely challenging. In this paper, we model the VRPTW-ST as a two-stage stochastic program and define two recourse policies to recover operations feasibility when the first stage plan turns out to be infeasible. To the best of our knowledge, we are the first to consider such a problem setting. We formulate the VRPTW-STas a set partitioning problem and solve it by exact branch-cut-and-price algorithms. Specifically, we developed efficient labeling algorithms by suitably choosing label components, determining extension functions, and developing lower and upper bounds on partial route reduced cost to be used in the column generation step. Results on benchmark data show that our methods are able to solve instances with up to 50 customers for both recourse policies.

R. C. Funes, M. A. S. Aguilar, and V. Boyer,

“Multi-Depot Periodic Vehicle Routing Problem with Due Dates and Time Windows,”

Journal of the Operational Research Society, Vol. 69, No. 2, pp.296-306, 2018

DOI:10.1057/s41274-017-0206-7      URL    

This paper introduces a variant of the well-known Multi-Depot Periodic Vehicle Routing Problem, which is inspired by a real situation of a distribution company. The problem consists in determining the

S. Gao,

“The Research of Vehicle Routing Problems with Time Windows based on Electric Vehicle,

” Dalian Maritime University, 2015

D. M. Miranda and S. V.Conceição,

“The Vehicle Routing Problem with Hard Time Windows and Stochastic Travel and Service Time,”

Expert Systems with Applications,Vol. 64,pp. 104-116,2016

DOI:10.1016/j.eswa.2016.07.022      URL    

In real-world environments, the variability is always present and influences the level and cost service offered to customers. In this scenario, the present work develops a strategy to solve the Vehicle Routing Problem with Time Windows (VRPTW) in which the travel time among the customers is known only probabilistically and the vehicles are not allowed to start the service before the earliest time windows. The fact there is waiting time brings a challenge to the model because the arrival time distribution at a customer can be truncated, affecting the arrival time in the following customers. A new method is developed to estimate the vehicle arrival time at each customer and to estimate the vehicle's probability to respect the customer's time window. The metaheuristic based on Iterated Local Search finds the best route with minimal expected cost, and it guarantees that certain levels of service are met. A benchmark is used to evidence the superior performance and accuracy of the proposed method.

V. A.Nguyen, J. Jiang, K.M. Teo,

“Satisficing Measure Approach for Vehicle Routing Problem with Time Windows under Uncertainty,”

European Journal of Operational Research,Vol.248,No. 2,pp. 404-414,2016

DOI:10.1016/j.ejor.2015.07.041      URL    

The complexity of evaluating chance constraints makes chance-constrained programming problem difficult to solve. One way to handle this complexity is by devising satisficing measures for the relevant uncertainties. This paper focuses on solving the stochastic vehicle routing problem with time windows (VRPTW) by Satisficing Measure Approach (SMA) that mitigates the dissatisfaction experienced by the customers. Satisficing measures are first proposed for the VRPTW with stochastic demand on various distributions to demonstrate the dependency of customers satisfaction towards lack of inventory based on the vehicle's capacity. Similar satisficing measures are extended to VRPTW with stochastic travel times. We integrate the proposed satisficing measures into an existing tabu-search heuristics to solve a set of generalized Solomon instances in a short amount of computation time. Compared with best-known results, the SMA saves the effort to design recourse actions, applicable to many popular probability distributions and produces very competitive results.

R. Spliet and A.F. Gabor,

“The Time Window Assignment Vehicle Routing Problem,”

Transportation Science,Vol.49,No. 4,pp. 721-731,2015

L. J.Tan, F.Y. Lin, H. Wang,

“BFO Optimization Algorithms for Vehicle Routing Problem with Time Windows,”

Applied Mechanics and Materials,Vol.543-547,pp. 1884-1887,2014

DOI:10.4028/www.scientific.net/AMM.543-547.1884      URL     [Cited within: 1]

Vehicle Routing Problem with Time Windows (VRPTW) is a constrained NP-hard problem that designs the least cost routes from one depot to a set of geographically scattered points. Most of traditional techniques are difficult to solve this kind of problem. In this paper, we explored the validity of another swarm-intelligence-based model-Bacterial Foraging Optimization (BFO) for VRPTW solving. Original BFO, BFO with linear decreasing chemotaxis step (BFO-LDC) and BFO with non-linear decreasing chemotaxis step (BFO-NDC) are used to obtain the best solutions of a given VRPTW problem, respectively. The experimental results demonstrated that the proposed BFO algorithms have the potential to solve Vehicle Routing Problem with Time Windows (VRPTW) with rapid convergence rate and the good result accuracy.

Y. B. Wang, J. M. Zhao, X. S. Jia, Y. Tian,

“Spare Parts Allocation Optimization in a Multi-Echelon Support System based on Multi-Objective Particle Swarm Optimization Method,”

Maintenance and Reliability, Vol.16, No. 1, pp.29-36, 2014

[Cited within: 1]

/