Printer Friendly

Analysis of an Automated Vehicle Routing Problem in Logistics considering Path Interruption.

1. Introduction

Due to fierce competition in the global market, an intelligent, efficient logistics system has become one of the most critical assets needed for an enterprise to stand out from others. The rapid development of the urbanisation and car ownership has produced big impacts on the transport systems, leading to challenges to many transport topics/areas, including demand management [1-3], traffic signalization [4, 5], traffic safety [6,7], and public transport [8-11]. Modern logistics industry asserts a strict claim to high efficiency.

Compared to conventional modes of transport, automated vehicles are proved to offer a huge improvement in service efficiency and quality. In dense urban cities, labour costs are high. Manpower is one of the significant elements in any logistics system, which undoubtedly leads to the high level of inputs into the logistics system. Additionally, fatigue driving and bad driving behaviours cause potential risks for the transportation safety, but automated vehicles are free from these worries. To be concluded, the application of automated vehicles in logistics can efficiently cut down the operation costs, improve the efficiency of freightage, and eliminate the potential risks caused by human beings. In this regard, the methodology of automated vehicle routing planning in logistics is proposed. Implementing automated equipment in the last mile can largely cut down the cost of the logistics and render the logistics system "smart" or "intelligent," which thus meets consumer expectations; however, unmanned equipment is still on the test bed. Defects and instabilities in the technology limit the scale of the application of automated vehicles in the initial period. According to a report of public views on automated vehicles from the American Automobile Association (AAA), 75% of interviewees hold pessimistic views on unmanned technology: 54% of drivers maintain that automated vehicles on real roads must increase the potential risk of a traffic accident and intensify public anxiety. Thus, selectively opening or prohibiting sections of road is an essential stage in the promotion of the use of automated vehicles.

The conventional VRP model is modified by considering a traffic interruption. The partial blocking of roads is considered as a constraint in the proposed model. This work focuses on the automated vehicle routing problem with time windows (AVRPTW) model of single distribution centremass client mode. The purpose of the distribution centre is to plan the driving circuit and satisfy the demands of all of the consumers: the objective function is to minimise the operational cost. Thus, we examine the similarity between the conventional VRP and the AVRPTW. The greatest difference is that AVRP model is faced with stricter constraint conditions, such as path interruption. Additionally, cost structure in VRP and AVRP is different: cost in the VRP model consists of dispatching and human costs. However, these costs are simplified in the AVRPTW model. Based on the fundamental particle swarm optimisation (PSO) algorithm, an improved PSO algorithm is designed by modifying the inertia weights and learning factors to improve the performance thereof. The AVRPTW model and the improved PSO algorithm are tested in a case study: their validity and practicability are certified. Additionally, the application of automated vehicles in logistics is proved to offer a huge improvement in efficiency and other benefits.

The paper is organised as follows: Section 2 summarises the literature review, in Section 3, the AVRPTW model considering a traffic interruption is formulated, Section 4 introduces the improved PSO algorithm, the AVRPTW model and improved PSO algorithm are applied in a case study in Section 5, and Section 6 draws the conclusions.

2. Literature Review

The application of unmanned vehicle technology and vehicle networking technology can effectively reduce the severity of traffic congestion, traffic accidents, and environmental pollution. Some scholars applied this technology to some fields of transportation. For example, unmanned vehicle technology was applied in intersection control to ensure the safety and efficiency thereof [12, 13]; however, as for last-mile logistics distribution, transportation, and other areas, the application of unmanned vehicles has not yet started.

Jozefowiez et al. [14] analysed a multiobjective path optimisation problem by comparing the definition of each problem, objectives, and algorithms [14]. Baldacci et al. [15] reviewed recent research into the exact algorithms for the VRP with capacity and time window constraints [15]. Nagy and Salhi [16] proposed an improved heuristic algorithm to solve the pick-up and delivery VRP with multiple depots [16].

In Europe, as a source of air pollution, transportation activities in the logistics sector activities account for 24% of all European emissions. In recent decades, more environmental problems related to economic activities have been transferred to the logistics field. Based on this background, a multiobjective vehicle routing problem was proposed [17]. Michallet et al. [18] studied a periodic VRP with time constraints in high value goods transportation. Archetti et al. [19] considered enterprises that not only used company drivers and delivery vehicles, but also allowed others willing to participate in one-way distribution runs, close to their delivery destination, so as to reduce the cost of distribution [19].

Considering a multivehicle scheduling problem, an example of a distribution enterprise was studied by Coelho et al. [20]. The problem consisted of a number of service constraints for specific customer requirements, considering fixed vehicle, and transportation costs. An adaptive search procedure with a local search and an improved process using a variable neighbourhood were designed. Coelho et al. [20] used this algorithm to derive an optimal transportation plan and reduced the cost thereof [20]. The path planning of an unmanned aerial vehicle (UCAV) was a complex global optimisation problem, which could be used to search for the optimal path on the field of combat. Zhang et al. [21] proposed a new heuristic algorithm to solve the wolf UCAV 2D path planning problem. Then, UCAV could avoid the threat by connecting the two-dimensional coordinates of the node, achieving the lowest cost while finding a safe path. The simulation results showed that the proposed method considered the quality, speed, and ultimate stability in path planning [21]. An energy-efficient path planning problem was developed: the experimental results showed that the method could save energy effectively [22]. In the last-mile logistics considering the use of electric cars as a means of conveyance, Klumpp [23] studied the logistics cost and undertook a sustainability evaluation [23]. A mixed integer linear programming optimisation algorithm was proposed to solve the VRP, to validate the algorithm. A periodic vehicle routing problem (PVRP) was used as a case study by Cacchiani et al. [24]. The results verified the effectiveness of the proposed algorithm and were the best known solutions [24]. The hybrid particle swarm optimisation algorithm was used to solve the conventional VRP [25].

VRP is an NP-hard problem, and a heuristic algorithm is usually needed to solve this kind of problem. Chen et al. [26] used system dynamics to modify the particle and established the adaptive particle swarm algorithm to solve the set of multiproduct material transport path optimisation problems. To minimise the total cost, corresponding constraints were set and this model algorithm was used to solve various problem instances, which further verified the effectiveness of the algorithm [26]. In order to generate an effective solution way to fix the VRPSPD, which was known as an NP-hard problem, Goksal et al. [27] proposed an approach which was a solution based on particle swarm optimisation algorithm. At the same time, an annealing strategy was used to maintain the diversity of population. The effectiveness of the algorithm was verified by experiments, and the optimal solution was obtained by using the improved ant colony algorithm [27]. Combined with a real-life application, Goel and Gruhn [28] studied the rich VRP. GVRP was a solution in the highly restricted search space, which was suggested to improve the iterative search process by changing the neighbourhood structure [28]. Although 2L-VRPB was often applied, few researchers studied this method. Based on this fact, Liu [29] proposed a hybrid metaheuristic algorithm to solve the problem and verified the effectiveness of the algorithm experimentally [29]. Cinar et al. [30] designed a finite time, two-phase, cumulative algorithm to solve the VRP and proposed a fast, easy way to implement their CumVRP-LD algorithm. The algorithm could change in response to changes in the actual situation; the high response speed was necessary to develop the system [30].

Yu et al. [31] proposed an improved ant colony algorithm to solve the VRP. The effectiveness of the algorithm was verified by the data of fourteen datum points [31]. Pisinger and Ropke [32] proposed a general heuristic algorithm to solve the following five kinds of VRP: VRP with time windows, capacity-limited VRP, multidepot VRP, site-dependent VRP, and open VRP [32]. Christian [33] established a relatively simple, but effective, hybrid genetic algorithm. In terms of the average cost, the performance of the hybrid genetic algorithm was better than that of most heuristic algorithms. It was proved that this algorithm was the best solution in 20 large cases studies [33]. Schyns [34] used the ant colony algorithm to solve the VRP including mixed batch arrival and dynamic capacity with time windows [34]. The ant colony algorithm is a metaheuristic algorithm, which was used to solve the VRP. Bell and McMullen [35] compared the ant colony algorithm with the TS search algorithm and genetic algorithm and found that the ant colony algorithm required less computation time [35]. Gribkovskaia et al. [36] proposed a mixed integer programming model (SVRPPD), which was compared with the classical algorithm and the improved heuristic algorithm. The results showed that the best solution was often generated by the heuristic algorithm [36]. Kumar et al. [37] used a self-learning particle swarm optimisation (PSO) algorithm to solve the multiobjective model of production and pollution, and the total operating cost was minimised [37].

Previous studies are limited with regard to their application in practice. To sum up, contributions of this paper are two twofold: (i) AVRPTW model considering a traffic interruption is built for the consideration of the policy restriction when applying automated vehicles in last-mile situations in the initial stage; (ii) an improved PSO algorithm is developed for the AVRPTW model with path interruption.

3. Mathematical Model for AVRPTW

3.1. Problem Statement. The automated vehicle routing problem (AVRP) model can be described as follows, and the model is shown in Figure 1: the total number of the consumers in one certain area is N; the distribution centre has to distribute a certain amount of goods to certain consumers; presently, this distribution centre is preparing to put in several automated vehicles to carry out the assignment. In the initial stage of the application of the automated vehicle, considering the restrictions imposed by the transportation policy, some sections among certain distribution paths can be seen as a break-off point, which is shown as the red line in Figure 1. Meanwhile, when vehicles arrive, consumers have to sign for the goods. Thus, the AVRP model can be identified as an automated vehicle routing problem with time windows (AVRPTW). Time windows are defined as [[e.sub.i], [l.sub.i]]. When the vehicle arrives before [e.sub.i], then a vehicle has to wait, which is the cause of the penalty cost. When the vehicle arrives after [l.sub.i], this distribution service is regarded as a failure. The distribution centre has to plan a certain path for each automated vehicle and all the consumer demands must be satisfied: the objective is to minimise the total cost of the operation.

Considering practical circumstances, several assumptions are made: each automated vehicle is assumed to have the same capacity. Additionally, the total load in one journey cannot surpass this value. Each automated vehicle starts from the distribution centre and must return there after the delivery. Besides, each consumer is only served by one automated vehicle. Considering policy restrictions, some paths among certain consumers are break-off points.

In addition, this model is defined as a VRP model with hybrid time windows. That is to say, when the vehicle arrives before [e.sub.i], the penalty cost and waiting time have a linear relationship. When the vehicle arrives after [l.sub.i], the penalty cost is seen as infinite. Considering the real operational process and the cost structure of a distribution centre, the total operating cost in this model is composed of three parts: fixed costs, transportation costs, and the penalty cost.

The notation in this paper is summarised in Notations.

3.2. AVRPTWModel with Path Interruption

[mathematical expression not reproducible] (1)

[mathematical expression not reproducible], (2)

[mathematical expression not reproducible], (3)

[mathematical expression not reproducible], (4)

[n.summation over (i=0)] [X.sub.i0k] [less than or equal to] 1 k = 1,2, ..., K, (5)

[mathematical expression not reproducible] (6)

[mathematical expression not reproducible] (7)

[mathematical expression not reproducible], (8)

[X.sub.ijk] = {0,1}, (9)

[X.sub.ghk] = 0 1, 2, ..., K, (10)

[T.sub.0k] = 0 k = 1, 2, ..., (11)

[T.sub.ik] [greater than or equal to] 0 i = 1, 2, ..., n k = 1, 2, ..., K. (12)

The objective function in (1) aims to minimise the fixed costs, transport costs, and penalty cost. Equation (2) implies that each consumer is only served by one automated vehicle. Equation (3) denotes the capacity limitation of each automated vehicle. Equation (4) requires that the total number of automated vehicles cannot surpass the sum of the vehicles that the distribution centre has at its disposal. Equation (5) implies that each path can only pass by the distribution centre once or not at all. Equation (6) shows that the number of vehicles entering a location equals the number of vehicles leaving it. Equation (7) defines the time windows. Equation (8) is the branch elimination constraint. Equation (9) defines the decision variables as binary values. Equation (10) denotes the interrupted paths. Equation (11) denotes the time when the automated vehicles leave the distribution centre. Equation (12) denotes that the time is nonnegative.

The conventional VRP model with hybrid windows is known as a combinational optimisation problem, which is an NP-hard problem and cannot be solved by simple algorithms. Clearly, solving the AVRP problem is also difficult; thus to solve the AVRP model, existing exact algorithms cannot efficiently obtain the solution. Therefore, heuristic algorithms are efficient ways of solving this NP-hard problem. The particle swarm optimisation algorithm offers excellent performance with regard to solving the various VRP models. Therefore, the PSO algorithm is adopted here to solve the AVRPTW model.

4. Solution Algorithm

4.1. The Particle Swarm Optimisation (PSO) Algorithm. The PSO algorithm is an evolutionary algorithm, which originates from research into bird flock preying behaviour. The PSO algorithm is similar to a genetic algorithm, both of which are based on iteration.

In the PSO algorithm, a particle swarm is initialised, which is also identified as the initial solution. Then the particle follows the best particle through iteration. For the ith particle in the dth dimension, the position vector and the velocity vector are defined as follows: [X.sup.i] = ([x.sub.i,1] [x.sub.i,2] ... [x.sub.i,d]) and [V.sup.i] = ([v.sub.i,1] [v.sub.i,2] ... [v.sub.i,d]). During each iteration, each particle refreshes itself by following the two types of best solutions: (i) the optimal solution for each individual and (ii) the optimal solutions of the population. After finding these two optimal solutions, the particle refreshes its position and velocity according to

[mathematical expression not reproducible], (13)

The specific steps are as follows.

Step 1. Random initialisation of the position and velocity of all particles.

Step 2. Calculation of the adaptive value for each particle and then storing the optimal solution of the present individual in pbest, while storing the optimal solution of the population in gbest.

Step 3. Refreshment of the position vector and velocity vector.

Step 4. Adjustment of the optimal solution of each individual.

Step 5. Adjustment of the optimal solution of the population.

Step 6. Execution of a stop-check as to whether, or not, the number of iterations is greater than the preset end value.

Step 7. Output and end.

4.2. The Improvement of the PSO Algorithm. The adjustable parameters in the PSO algorithm include learning factors [c.sub.1], c2 and an inertia weight w. Inertia weight is used to control the impact of histories of velocities on the current velocity. The particle adjusts its trajectory based on information about its previous best performance and the best performance of its neighbours. Learning factors, [c.sub.1] and [c.sub.2], decide how the interaction between the particle itself and its neighbour affects the adjustment of both position and velocity. Thus, they are used to control the convergence behaviour of the PSO. And the function y = cos x is applied to adjust the inertia weight and learning factors.

(1) The Improvement of Inertia Weight. Apply y = cos x in the formula for the inertia weight, and the improved expression for inertia weight is given by

W = [C.sub.max] - ([w.sub.max] - [w.sub.min]) cos ((t/T -1)[pi]), (14)

where [w.sub.max] and [w.sub.min] denote the maximum and the minimum inertia weight, respectively: these two values are defined as 0.9 and 0.4 according to the last experienced value. The range of t/T is [0,1].

(2) The Improvement of Learning Factors. According to the improvement of inertia weight, the calculation of learning factors is given by

[c.sub.1] = [c.sub.1max] - ([c.sub.1max] - [c.sub.1min]) cos ((t/T)-1)[pi], [c.sub.1] = [c.sub.2]. (15)

4.3. The PSO Algorithm for AVPRTW Model. Applying the PSO algorithm to solve the AVRP model, it is vital to realise that each particle should be in correspondence with its coding. Two spatial vectors are designed to represent the solution: k denotes the number of the vehicle for each path, while r denotes the precedence order of vehicle arrival at the consumers. These two spatial vectors are [X.sub.k] and [X.sub.r]. To illustrate the coding, an example is given; assuming that there are 10 consumers in this area and the distribution centre is equipped with three vehicles, we assume an optimal solution as follows:

[X.sub.k] 1 3 3 2 2 3 3 1 1 1

[X.sub.r] 2 3 2 1 2 4 1 4 1 3 (16)

The optimal solution denotes that all of the three vehicles are assigned to execute the distribution task. The first vehicle serves consumers 1, 8, 9, and 10. The second vehicle serves consumers 4 and 5, and consumers 2, 3, 6, and 7 are served by the third vehicle. According to [X.sub.r], the distribution order of the first vehicle is 0 [right arrow] 9 [right arrow] 1 [right arrow] 10 [right arrow] 8 [right arrow] 0, that of the second vehicle is 0 [right arrow] 4 [right arrow] 5 [right arrow] 0, and that of the third vehicle is 0 [right arrow] 7 [right arrow] 3 [right arrow] 2 [right arrow] 6 [right arrow] 0.

The specific steps are as follows.

Step 1 (initialisation of the particle swam). Firstly, several parameters of the PSO algorithm have to be set, including the population, the maximum number of iterations, and the spatial dimension. [X.sub.k] and [X.sub.r] are, respectively, confined to [1, K] and [1, N]. The corresponding velocity vectors [V.sub.k] and [V.sub.r] are, respectively, confined to [-(-K-1), (K-1)] and [-(N-1),(N-1)].

Step 2. According to (14) and (15), the position and velocity are refreshed. The refreshed values of position and velocity are substituted into the fitness function and the optimal value of each individual and the population are initialised.

Step 3. Compare the adaptive value with its optimal value, and refresh pbest.

Step 4. Calculate the refreshed optimal value of the population, compare this value to the present gbest, and refresh the value of gbest.

Step 5. Judge whether, or not, the maximum number of iterations has been reached, and if so, output the optimal solution (otherwise, return to Step 2).

5. Case Study

5.1. Background Information. One certain chain supermarket has one distribution centre (DC) in this area and there are 25 stores. The distribution centre adopts a self-distribution strategy and has to schedule deliveries and plan the path of each vehicle, so that all demands from the 25 stores are satisfied. The geographical position of the distribution and all stores are shown in Figure 2 and the position coordinates are simplified and specific data are given in Table 1.

In the practical delivery operation, considering the employee cost and risk cost caused by fatigue while driving, the enterprise is preparing to assign several automated vehicles in these real services. Due to anxiety from the public, prohibited sections are used in the initial stage and break-off sections are marked by the red dotted line in Figure 2. Each store should arrange some people to be on duty within a specific time frame, the time windows, and the service time of each store is given in Table 1.

5.2. Analysis of the Case Study. Based on the AVRPTW model, the improved PSO algorithm is used to solve the problem. To simplify the calculation, some parameters of the model are assumed when carrying out the experimental test. The specific parameters of the model are as listed in Table 2. With the help of MATLAB[TM] 2015b, this problem is solved and the solutions are given in Figure 3 and Table 3.

5.3. Analysis and Discussion. According to the solution, the distribution centre has to allocate four automated vehicles to execute the task. All of the stores are included in these planned paths. Based on Figure 3, after the 145th iteration, the algorithm converges and the optimal solution is given. The minimum total cost is 11,328. From Figure 3, it is seen that the convergence performance of the PSO algorithm is good, and its antijamming capability is realised.

Considering four paths are interrupted, a total four automated vehicles are assigned to serve all the stores, and the load factor of each one is 76%, 76%, 80%, and 100%, respectively. The capacities of the automated vehicles are almost fully utilised. The results show that the transportation resources available have been used to full advantage.

6. Conclusion

Considering the partial sections interruption and the time windows in the initial stage of the application of automated vehicles in last-mile mode, the conventional VRP model is modified. The AVRPTW model with traffic interruptions is established. Additionally, an improved PSO algorithm is designed by changing the inertia weight and learning factors. Finally, a case study has been analysed and the validity and practicability of the mathematical model and algorithm have been verified.

Due to the immaturity of unmanned vehicle technology, the promotion and popularisation of automated vehicles in real applications are likely to be faced with strict restrictions in the initial stage. First, it is inevitable that automated vehicles must exert a negative influence on the public and general transport environment. Second, the potential risks caused by traffic congestion and the unregulated behaviour of other drivers are likely to affect the promotion of such unmanned technology and unmanned vehicles in general. Accordingly, a policy that partially opens, or restricts, road sections for automated vehicles can both ensure the safety of the automated vehicles and reduce anxiety about unmanned vehicle technology from the public. Thus, it is of practical significance to study automated vehicle route problems.

Apart from the aforementioned problems, there may also be other issues that must be taken into consideration when applying unmanned vehicles in the logistics sector, such as the influence that automated vehicles have on ordinary vehicles and the safety of automated vehicles. These issues should be addressed in future research.

i, j:          The number of consumers, where 0
                 denotes the distribution centre,
                 i,j = 0, 1, 2, ..., N
k:             The number of the automated vehicles,
                 k= 1, 2, 3, ..., K
[x.sub.ijk]:   [x.sub.ijk] = 1 if arc(i, j) is in the path of the kth
                 automated vehicle, and [x.sub.ijk] = 0 otherwise
[d.sub.i]:     The delivery to the ith consumer
Q:             The capacity of each automated vehicle
[f.sub.i]:     The service time to the ith consumer
[t.sub.ij]:    The transport time from the ith consumer
                 to the jth consumer
[s.sub.i]:     The earliest service time of the ith
[l.sub.i]:     The latest service time of the ith consumer
[alpha]:       The index of the penalty function
M:             The infinite value
a:             The fixed cost of one automated vehicle
[T.sub.ik]:    The time when the kcth vehicle arrives at the
                 ith consumer.

Conflicts of Interest

The authors declare that they have no conflicts of interest regarding the publication of this paper.


This research is supported by the National Natural Science Foundation of China (no. 71372198) and the Science and Technology Department of Jiangsu Province, China (no. BY2015070-25).


[1] S. Wang, "Efficiency and equity of speed limits in transportation networks," Transportation Research C, vol. 32, pp. 61-75, 2013.

[2] Z. Liu, Q. Meng, and S. Wang, "Speed-based toll design for cordon-based congestion pricing scheme," Transportation Research Part C: Emerging Technologies, vol. 31, pp. 83-98, 2013.

[3] Z. Liu, S. Wang, B. Zhou, and Q. Cheng, "Robust optimization of distance-based tolls in a network considering stochastic day to day dynamics," Transportation Research Part C: Emerging Technologies, vol. 79, pp. 58-72, 2017.

[4] Y. Bie, D. Wang, and X. Qu, "Modelling correlation degree between two adjacent signalised intersections for dynamic subarea partition," IET Intelligent Transport Systems, vol. 7, no. 1, pp. 28-35, 2013.

[5] Y. Bie, Z. Liu, and L. Lu, "A signal coordination algorithm for adjacent hook-turn intersections," Journal of Advanced Transportation, vol. 50, no. 2, pp. 197-213, 2016.

[6] X. Qu, Q. Meng, and Z. Liu, "Estimation of number of fatalities caused by toxic gases due to fire in road tunnels," Accident Analysis and Prevention, vol. 50, pp. 616-621, 2013.

[7] X. Qu, Y. Yang, Z. Liu, S. Jin, and J. Weng, "Potential crash risks of expressway on-ramps and off-ramps: a case study in Beijing, China," Safety Science, vol. 70, pp. 58-62, 2014.

[8] Y. Bie, X. Gong, and Z. Liu, "Time of day intervals partition for bus schedule using GPS data," Transportation Research Part C, vol. 60, pp. 443-456, 2015.

[9] S. Jin, X. Qu, D. Zhou, C. Xu, D. Ma, and D. Wang, "Estimating cycleway capacity and bicycle equivalent unit for electric bicycles," Transportation Research A: Policy and Practice, vol. 77, pp. 225-248, 2015.

[10] Z. Liu, S. Wang, W. Chen, and Y. Zheng, "Willingness to board: a novel concept for modeling queuing up passengers," Transportation Research Part B, vol. 90, pp. 70-82, 2016.

[11] S. Wang and X. Qu, "Station choice for Australian commuter rail lines: equilibrium and optimal fare design," European Journal of Operational Research, vol. 258, no. 1, pp. 144-154, 2017.

[12] K. Yang, S. I. Guler, and M. Menendez, "Isolated intersection control for various levels of vehicle technology: conventional, connected, and automated vehicles," Transportation Research Part C: Emerging Technologies, vol. 72, pp. 109-129, 2016.

[13] Y. Zheng, L. Jin, L. Gao, K. Li, Y. Wang, and F. Wang, "Development of a distributed cooperative vehicles control algorithm based on V2V communication," Procedia Engineering, vol. 137, pp. 649-658, 2016.

[14] N. Jozefowiez, S. Frederic, and E.-G. Talbi, "Multi-objective vehicle routing problems," European Journal of Operational Research, vol. 189, no. 2, pp. 293-309, 2008.

[15] R. Baldacci, A. Mingozzi, and R. Roberti, "Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints," European Journal of Operational Research, vol. 218, no. 1, pp. 1-6, 2012.

[16] G. Nagy and S. Salhi, "Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries," European Journal of Operational Research, vol. 162, no. 1, pp. 126-141, 2005.

[17] J. C. Molina, I. Eguia, J. Racero, and F. Guerrero, "Multi-objective vehicle routing problem with cost and emission functions," Procedia--Social and Behavioral Sciences, vol. 160, pp. 254-263, 2014.

[18] J. Michallet, C. Prins, L. Amodeo, F. Yalaoui, and G. Vitry, "Multi-start iterated local search for the periodic vehicle routing problem with time windows and time spread constraints on services," Computers and Operations Research, vol. 41, no. 1, pp. 196-207, 2014.

[19] C. Archetti, M. Savelsbergh, and M. . Speranza, "The vehicle routing problem with occasional drivers," European Journal of Operational Research, vol. 254, no. 2, pp. 472-480, 2016.

[20] V. N. Coelho, A. Grasas, H. Ramalhinho, I. M. Coelho, M. J. F. Souza, and R. C. Cruz, "An ILS-based algorithm to solve a large-scale real heterogeneous fleet VRP with multi-trips and docking constraints," European Journal of Operational Research, vol. 250, no. 2, pp. 367-376, 2016.

[21] S. Zhang, Y. Zhou, Z. Li, and W. Pan, "Grey Wolf optimizer for unmanned combat aerial vehicle path planning," Advances in Engineering Software, vol. 99, pp. 121-136, 2016.

[22] H. Niu, Y. Lu, A. Savvaris, and A. Tsourdos, "Efficient path planning algorithms for unmanned surface vehicle," IFAC-PapersOnLine, vol. 49, no. 23, pp. 121-126, 2016.

[23] M. Klumpp, "Electric mobility in last mile distribution," Efficiency and Innovation in Logistics, pp. 3-13, 2014.

[24] V. Cacchiani, V. C. Hemmelmayr, and F. Tricoire, "A set-covering based heuristic algorithm for the periodic vehicle routing problem," Discrete Applied Mathematics, vol. 163, part 1, pp. 53-64, 2014.

[25] Y. Marinakis and M. Marinaki, "A hybrid genetic - particle swarm optimization algorithm for the vehicle routing problem," Expert Systems with Applications, vol. 37, no. 2, pp. 1446-1455, 2010.

[26] M.-C. Chen, Y.-H. Hsiao, R. H. Reddy, and M. K. Tiwari, "The self-learning particle swarm optimization approach for routing pickup and delivery of multiple products with material handling in multiple cross-docks," Transportation Research Part E: Logistics and Transportation Review, vol. 91, pp. 208-226, 2016.

[27] F. P. Goksal, I. Karaoglan, and F. Altiparmak, "A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery," Computers & Industrial Engineering, vol. 65, no. 1, pp. 39-53, 2013.

[28] A. Goel and V. Gruhn, "A general vehicle routing problem," European Journal of Operational Research, vol. 191, no. 3, pp. 650-660, 2008.

[29] S.-X. Liu, "Variable neighborhood search for solving vehicle routing problems with backhauls and time windows," Journal of Northeastern University, vol. 29, no. 3, pp. 316-319, 2008.

[30] D. Cinar, K. Gakis, and P. M. Pardalos, "A 2-phase constructive algorithm for cumulative vehicle routing problems with limited duration," Expert Systems with Applications, vol. 56, pp. 48-58, 2016.

[31] B. Yu, Z. Yang, and B. Yao, "An improved ant colony optimization for vehicle routing problem," European Journal of Operational Research, vol. 196, no. 1, pp. 171-176, 2009.

[32] D. Pisinger and S. Ropke, "A general heuristic for vehicle routing problems," Computers & Operations Research, vol. 34, no. 8, pp. 2403-2435, 2007.

[33] P. Christian, "A simple and effective evolutionary algorithm for the vehicle routing problem," Computers & Operations Research, vol. 31, no. 12, pp. 1985-2002, 2004.

[34] M. Schyns, "An ant colony system for responsive dynamic vehicle routing," European Journal of Operational Research, vol. 245, no. 3, pp. 704-718, 2015.

[35] J. E. Bell and P. R. McMullen, "Ant colony optimization techniques for the vehicle routing problem," Advanced Engineering Informatics, vol. 18, no. 1, pp. 41-48, 2004.

[36] I. Gribkovskaia, 0. Halskau Sr., G. Laporte, and M. Vlcek, "General solutions to the single vehicle routing problem with pickups and deliveries," European Journal of Operational Research, vol. 180, no. 2, pp. 568-584, 2007.

[37] R. S. Kumar, K. Kondapaneni, V. Dixit, A. Goswami, L. S. Thakur, and M. K. Tiwari, "Multi-objective modeling of production and pollution routing problem with time window: a self-learning particle swarm optimization approach," Computers and Industrial Engineering, vol. 99, pp. 29-40, 2016.

Yong Zhang, Lei Shi, Jing Chen, and Xuefeng Li

School of Transportation, Southeast University, Nanjing, China

Correspondence should be addressed to Lei Shi;

Received 27 April 2017; Accepted 2 July 2017; Published 7 August 2017

Academic Editor: Vinayak Dixit

Caption: FIGURE 1: AVRPTW model diagram.

Caption: FIGURE 2: Locations of the distribution centre and consumers.

Caption: FIGURE 3: Convergence of the solution algorithm.
TABLE 1: Position coordinates and time windows.

Number   Coordinate   Earliest   Latest   Demand   Service time

DC        (35, 35)       --        --       --          --
1         (41, 49)      161       171       10          10
2         (35, 17)       50        60        7          10
3         (55, 45)      116       126       13          10
4         (55, 20)      149       159       19          10
5         (15, 30)       34        44       26          10
6         (25, 30)       99       109        3          10
7         (20, 50)       81        91        5          10
8         (10, 43)       95       105        9          10
9         (55, 60)       97       107       16          10
10        (30, 60)      124       134       16          10
11        (20, 65)       67        77       12          10
12        (50, 35)       63        73       19          10
13        (30, 25)      159       169       23          10
14        (15, 10)       32        42       20          10
15         (30, 5)       61        71        8          10
16        (10, 20)       75        85       19          10
17         (5, 30)      157       167        2          10
18        (20, 40)       87        97       12          10
19        (15, 60)       76        86       17          10
20        (45, 65)      126       136        9          10
21        (45, 20)       62        72       11          10
22        (45, 10)       97       107       18          10
23        (55, 5)        68        78       29          10
24        (65, 35)      153       163        3          10
25        (65, 20)      172       182        6          10

TABLE 2: Model parameters.

Parameter                                Value

Fixed cost of each automated vehicle      200
Index of the penalty function             1.5
Capacity                                  100
Transport cost per unit hauled             8
Average speed of an automated vehicle     40

TABLE 3: Paths and load factors.

Number                     Path                     Load factor (%)

1          0 [right arrow] 24 [right arrow] 17            76
         [right arrow] 23 [right arrow] 18 [right
         arrow] 21 [right arrow] 4 [right arrow]

2           0 [right arrow] 11 [right arrow] 1            76
          [right arrow] 7 [right arrow] 5 [right
                arrow] 13 [right arrow] 0

3           0 [right arrow] 20 [right arrow] 9            80
         [right arrow] 10 [right arrow] 3 [right
         arrow] 12 [right arrow] 2 [right arrow]

4          0 [right arrow] 16 [right arrow] 14            100
         [right arrow] 15 [right arrow] 19 [right
          arrow] 8 [right arrow] 6 [right arrow]
           22 [right arrow] 25 [right arrow] 0
COPYRIGHT 2017 Hindawi Limited
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2017 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Research Article
Author:Zhang, Yong; Shi, Lei; Chen, Jing; Li, Xuefeng
Publication:Journal of Advanced Transportation
Article Type:Report
Date:Jan 1, 2017
Previous Article:A Variable Interval Rescheduling Strategy for Dynamic Flexible Job Shop Scheduling Problem by Improved Genetic Algorithm.
Next Article:A Continuous Deviation-Flow Location Problem for an Alternative-Fuel Refueling Station on a Tree-Like Transportation Network.

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters |