iBusiness, 2013, 5, 8489 http://dx.doi.org/10.4236/ib.2013.53B018 Published Online September 2013 (http://www.scirp.org/journal/ib) An Algorithm to Vehicle Scheduling Problem of AirPort Pickup and Delivery Service Zhengzheng Xu1,2*, Jiafu Tang2 1School of Business Administration, Northeastern University, Shenyang 110819, China; 2State Key Laboratory of Integrated Auto mation for Process Industries, Northeastern University, Shenyang 110819, China. Email: *xuzz99@sina.com Received July, 2013 ABSTRACT This paper studies the vehicle scheduling problem in cities for the pickup and delivery service. Considering customer point as vehicle collaboration point, we propose a twostage algorithm based on customer point collaboration through the theory of optimization. In additio n to considering the problem whether the isolated customer point is collabo rative, the algorithm also takes into account the problem whether the customers on the vehicle (picking up multiple customer points) can transfer its customers to the other basic vehicle. Moreover, the selection of the type of basic vehicles is no longer single; we can choose different types of vehicles suitable for different vehicle capacities according to the total number of people to carry. Finally, we perform simulation analysis and simulation results show that th e algorithm pro posed in this paper is feasible and effective. Keywords: Pickup and Delivery Service; Vehicle Collaboration; Satisfaction Degree; Isolated Customer Point 1. Introduction The airport pickup and delivery service is a valueadded service for the air ticket corporation to attract customers and enhance market competitiveness. The vehicle sched uling in the airport pickup and delivery service is sig nificantly important for the modern logistics engineering and transportation. And it has received the extensive at tention and studied well. The vehicle routing and sched uling problem of pickup and delivery of customers to airport belongs to the vehicle routing problem [1]. Some vehicles and trip number are unnecessary for the whole pickup and delivery service [2]. The vehicle scheduling problem is similar to the routing prob lem in communica tion networks where we are to find the optimal route ac cording to the origindestination flows [3, 4]. In the pickup and delivery service for customers, the vehicle scheduling via vehicle collaborations has received exten sive attentions from academic and industrial circles. Some vehicle scheduling methods have been proposed to this problem. Belfiore et al. studied the longhaul ve hicle scheduling problems with working time rules [2]. Pop et al. used the integer programming to model the generalized vehicle routing problem and proposed two new models [1]. Wy et al. investigated the rollonrolloff vehicle routing problem and brought forth a hybrid metaheuristic approach to overcome it [5]. Mester et al. studied both capacitated vehicle routing problem and vehicle routing problem with time window constraints, and then they presented an efficient evolution strategies algorithm to solve them [6]. The setpartitioning model was used to find the optimal vehicle routing and sched uling in the free pickup and delivery service in flight ticket sales companies [7]. Yan et al. studied the cash transportation vehicle routing and scheduling, and they developed a model to ensure cash conveyance safety and minimize the transportation cost [8]. This paper studies the vehicle scheduling problem in cities for the pickup and delivery service. We propose the concept of the isolated customer point through taking customer satisfaction and bypass limit as constraints. Considering customer point as vehicle collaboration point, we propose the vehicle collaboration rules about customer transfer. And a twostage algorithm based on customer point collaboration is put forward through the theory of optimization. In addition to considering the problem whether the isolated customer point is collabo rative, the algorithm also takes into account the problem whether the customers on the vehicle (picking up multi ple customer points) can transfer its customers to the other basic vehicle. Moreover, the selection of the type of basic vehicles is no longer single; we can choose differ ent types of vehicles suitable for different vehicle capac ity according to the total number of people to carry. Fi nally, taking the airport p ick up an d deliv ery serv ice of air Copyright © 2013 SciRes. IB
An Algorithm to Vehicle Scheduling Problem of AirPort Pickup and Delivery Service 85 ticketing company as a study case, we perform simula tion analysis. Simulation results show that the algorithm proposed in this paper is feasible and effective. 2. Problem Statement Consider as the research object the traveling passengers of a city to pickup and deliver in a plan period (one day). According to the basic traveling information of passen gers (such as the traveling time and the pickup location of customers) in the plan period, air ticketing company is to arrange the number of vehicles dispatched, the depar ture time of each vehicle, customers to be picked up by each vehicle, pickup order for these customers, customer points to collaborate, selection of collaboration location s, and the pickup time. As a result, the company can achieve the high customer satisfaction degree and low operation cost. Basic vehicles are the vehicles that pick up customers from the depot to the airport. Collaborative vehicles refer to the vehicles that assist the basic vehicle to finish the pickup task from the depot but not arriving at the airport. Hence, for the characteristics of the prob lem itself, we give the following assumptions: In the pickup service, there is only one depot and one airport. Take the customers with the same pickup time in same location as the same customer point; the number of customers at each customer point is no more than the carrying capacity of each vehicle. Each vehicle serves one trip loop, and the whole process that the vehicle departs from the depot, arrives at the airport, and finally returns to the d epot is regarded as one trip. Employ two kinds of vehicles, and collaborative vehicles select the vehicles with smaller vehicle capacity. The number of customers in basic vehicle is greater than or equal to the number of customers in its collabora tive vehicle. During the whole pickup process, vehicles keep a constant speed and provide the service on time. Ignore the boarding time, and do not consider the delay and wait. Do not take the time required to transfer customers in the case of vehicle collaboration. Basic vehicles and collaborative vehicles will meet in the ideal state, namely without the waiting time. Based on the above assumptions, this paper will study how to perform the collaboration between basic vehicles and collaborative vehicles at customer point during the pickup service of the single trip, in order to obtain the optimal routing and scheduling methods of the single trip and multiple vehicles. In this section, the customers’ satisfaction degree about the time arriving at the airport is used to measure whether customers are satisfied with the pickup service or not. And we can use the satisfaction degree function to describe the satisfaction degree of customers [8]. Con sidering the factor of vehicle collaboration and the satis faction degree of customers at customer points, the satis faction degree function of the customers at customer point i based on the vehicles collaboration at customer points ca n be defined as: '' ' '' ' '' 1 [,] (1) [,] () (1) [,] 0 [,] ii ii iii ii i ii iii ii iii pt et ptee ee St lt ptll ll tel ii i i el 1 (1) where pi is a constant and ; when the cus tomers at customer point i need not transfer, pi = 0, oth erwise pi >0; 0 i p , ii el and , ii el eel , respectively, indicate the soft time window [9] and hard time window [10] of reaching the airport, meeting . iiii Assume that U represents the duration of the work plan within a planning period (typically one day), l C 1, 2,, n indicates the customer point set, 0 represents the depot, 0NC denotes the set of customer points and the depot, –1 represents the airport, 01NC denotes the set of all geographical locations during the customer pickup, i represents the number of customers at customer point i, is the level value of satisfaction degree that can be accepted by cus tomers, 1, 2,, B n represents the basic vehicle set, 1, 2,, C m Q is the collaborative vehicle set, C denotes the passenger capacity of collaborative ve hicles, Q represents the maximum passenger capacity between the two kinds of basic vehicles, ij is the travel time from customer point i to customer point j, dij repre sents the path distance form customer point i to customer point j, ik T denotes the arrival time of vehicle k to cus tomer point i, represents the bypass coefficient of customer pickup. Additionally, we assume that zk, yik, xijk, and vijk are the 01 variables and they are the decision variables of vehicle k. When vehicle k is used, 1 k z ; when the customers at customer point i is picked up by vehicle k, 1 ik y ; when basic vehicle k arrives form customer points i to j, 1 ijk x ; when collaborative vehi cle k arrives form customer points i to j, 1 ijk v . In the collaboration process, the following constraints of col laboration are considered: (), i Sti C (2) , iik BB iC yQ kK (3) , iik Cc iC QkK (4) Copyright © 2013 SciRes. IB
An Algorithm to Vehicle Scheduling Problem of AirPort Pickup and Delivery Service 86 (1) () , BC iikiki kK K tyTi C (5) Equation (2) denotes the constraints of customers’ sat isfaction degree. Equation (3) describes the constraints of the basic vehicles’ capacity. Equation (4) denotes the constraints of the collaborative vehicles’ capacity. Equa tion (5) is the limit of bypass time. This paper designs a twostage heuristic algorithm based on customer point collaboration. Customer point collaboration refers to the collaborative method that the collaborative vehicle transfers customers in it to the basic vehicle at a certain customer point. The first stage ex ploits the time sortingbased heuristic algorithm of prior clustering to generate the initial vehicle trips and access order of the customer points in each trip. The algorithm steps are as follows: Step 1: Give the information of customer points, the lower limit of satisfaction degree, and bypass limit coefficient . Calculate the time window of arriving at airport that meets the lower limitation of satisfaction de gree according to Equations (1) and (2). Step 2: Sort the customer points in order according to the lower limit of the time window of arriving at airport. And form the sequence K. Step 3: If K is empty, stop and output the results. Step 4: Select the first customer point in K as the clus tering point. Generate the set i according to the sort ing sequence of other customer points and the capacity limit of basic vehicles shown in Equation (3). Here the capacity of basic vehicle is limited to . S B Step 5: if i is not empty, we conduct full array of the customer pints in i, select the route with the short est driving distance and denote it as , and examine whether customer point Qx SSi r i () meets the bypass limitation in Equation (5). If cr1,2,j..., i r c meets the constraint, then keep it in i. Or otherwise remove r c S from i and i and put it into the set E. After finishing the whole process, put i into the route set R. When i, put this customer point into the set E, delete i, and delete this customer point from K. This is because the customer point is considered as the isolated customer point and is put into E if there is only one custo mer poin t in the route. S 1 rr S Step 6: Delete from K the customer points that have formed the cluster. Step 7: Put the customer points in E in the time order according to the lower limit of time window of arriving at airport and form the sequence L. According to the constraints in Equations (2)(5), select the customer point j to insert the route in R. Then form the new route, update the route set R, delete the customer points eE e from E and L, and go back to Step3. Step 8: Conduct the second clustering for the cus tomer points in E. Namely, repeat th e ab ov e Step s 27 for the customer points in E. If the customer points in E can form the new routes, then put these new routes into set R and delete the corresponding customer points from E and L. At the first stage, we get the basic path set R and iso lated point set E. At the second stage, we mainly con sider the customer satisfaction degree, vehicle capacity limitation, and bypass constraint based on the first stage. Using the selection rules of collaborative points, rear range the route for the isolated points in a collaborative way. Then we take into account the possible collabora tion between the collaborative vehicle picking up the customers of multiple customer points and the basic ve hicle, and make the appropriate scheduling. The heuristic algorithm steps at the second phase are as follows: Step 1: According to the isolated points in set E, con sider the change of customers’ satisfaction degree due to the vehicle collaboration. And recalculate the time win dow of arrive at the airport. Step 2: If L is empty, then remove all the basic path in path set R collaborated by the isolated point to set R2, output the result, and exit. Step 3: Take out the isolated point from L in order, insert the basic path that has the same time window with this isolated point and meet the vehicle capacity con straints. According to the above Rules 13, select the appropriate the collaborative point, build the corre sponding collaborative path, write down the basic path collaborated with isolated point, mark the collaborative customer point, remove this isolated point from set E to collaborative path set 1, update the arrival time win dow and the total number of the basic path which has been collaborated in set R. If not meeting the Rules 13, the isolated point does not participate in collaboration, separately construct the path, and place the built path into the path set R. R Step 4: Delete isolated points which have collaborated with basic path from L and E, and then go back to Step 2. Step 5: Reorder the path in R according to the lower limit of the arrival time window. Step 6: Take the path form R. If is empty, output the result and exit. i Ri R Step 7: Calculate a i wf where denotes arrival time window of the path i and f represents penalty factor. Build the intersection set i of and the time window of the existing path in . If i is not empty and the vehicle capacity constraint is satisfied, go to Step 4, or otherwise go back to Step 6. a i w 2R RUa i wfU Step 8: Select the customer point r in as the col laborative point. According to Rules 13, choose the col laborative point i which make the collaborative mile age shortest and all customer points in i meet the by pass restrictions. if i is found, construct the collabora tive path, write down the basic path and collaborative 2R R C C Copyright © 2013 SciRes. IB
An Algorithm to Vehicle Scheduling Problem of AirPort Pickup and Delivery Service Copyright © 2013 SciRes. IB 87 customer points collaborated by , and remove r from R to the collaborative path set , update the arrival time window and the total customer number of the basic path collaborated in . If i is not found, the path remains in R, and go back to Step 6. i R3R R R 2R i C f i R points. Thus the optimal adjustment is performed for the vehicle scheduling result formed at the first stage. The vehicle routing and scheduling problem of the single trip and multiple vehicles with the hybrid vehicle kinds is solved. Step 9: Take i from R. If i is empty, remove all the basic paths in R collaborated by the other basic paths into the path set , output the result and exit. R 5R3. Simulation Results and Analysis Here we use the pickup and delivery service of the air port as a study case to validate our algorithm. Assume there are 30 customer points to pick up for the flights of a period of 8:00  20:00, these customer points are distrib uted in the 55 55km km rectangular area, soft time window width is 20 minutes, hard time window width is 40 minutes, maximum capacity of basic vehicles is 8 B Q , maximum capacity of collaborative vehicles is 4 C Q , depot coordinate is (35,37), airport coordinate is (50,50), vehicle speed is , lower limit of cus tomers’ satisfaction degree is 60 /km h 0.8 , bypass restriction coefficient is 1.5 and . 0.1 i p Step 10: If has been collaborated, go to Step 9. i Step 11: Calculate where denotes the arrival time window of the path i and f represents the penalty factor. Build the intersection set Ra wa i w i U of a i wf and the time window of the basic paths in R except i. If R i U is empty or the vehicle capacity constraint is not satisfied, go back to Step 9. Step 12: Select the customer point z from the basic paths in R except i in order as the collaborative point. By Rules 13, choose the collaborative point i R which make the collaborative mileage shortest and all customer points in i meet the bypass restrictions. If i R is found, construct the collaborative path, write down the basic path and collaborative customer points collaborated by i, and remove z from R to the collaborative path set , update the arrival time window and the total customer number of the basic path collaborated in R. If i R The corresponding information of 30 customer points is shown in Table 1. To facilitate the statement, we give the abbreviations in the follow tables as follows: CP: Customer Point; VCP: Vehicle Coordination Point; LCP: Location of Customer Point; LHW: Lower bound of Hard time Windows; LSW: Lower bound of Soft time Windows; USW: Upper bound of Soft time Windows; UHW: Upper bound of Hard time Windows; NC: Num ber of Customers; VN: Vehicle Number; COP: Collabo ration Point. Using the firstphase algorithm without the vehicle collaboration, we generate the initial trip and the access sequence of customer points in each trip. Then the minimum running mileage and average utilization ratio of vehicle capacity are attained when not considering the vehicle collaboration. Average utilization ratio of vehicle capacity can be denoted as: 4R is not found, the path remains in R, and go back to Step 9. i In summary, through the three parts at the second phase, we finally get the set of the basic paths not participating collaboration, collaborative set collaborating with the basic paths, the collaborated basic path set R ' R 5R RR DR 13CR RR42 . Consequently, according to the number of customers on each path of R and D, we can determine how to choose the kinds of ba sic vehicles. According to the information in C, we can determine the collaborative path and co llaborative custo mer Table 1. Information of customer points. CP 1 2 3 4 5 6 7 8 9 10 LCP (42,34) (43,45) (30,25) (35,44)(39,36)(31,50)(34,30)(44,16)(29,51) (45,52) LHW 7:25 7:35 8:50 7:20 7:30 9:05 8:30 8:45 8:50 8:55 LSW 7:35 7:45 9:00 7:30 7:40 9:15 8:40 8:55 9:00 9:05 USW 7:55 8:05 9:20 7:50 8:00 9:35 9:00 9:15 9:20 9:25 UHW 8:05 8:15 9:30 8:00 8:10 9:45 9:10 9:25 9:30 9:35 NC 2 1 1 1 2 1 3 1 1 1 CP 11 12 13 14 15 16 17 18 19 20 LCP (27,33) (32,21) (42,40) (35,40)(14,10)(47,35)(35,40)(38,30)(26,30) (46,38) LHW 11:40 18:00 17:25 10:25 16:15 17:00 17:15 15:40 12:25 11:05 LSW 11:50 18:10 17:35 10:35 16:25 17:10 17:25 15:50 12:35 11:15 USW 12:10 18:30 17:55 10:55 16:45 17:30 17:45 16:10 12:55 11:35 UHW 12:20 18:40 18:05 11:05 16:55 17:40 17:55 16:20 13:05 11:45 NC 2 1 1 2 1 1 1 2 2 2 CP 21 22 23 24 25 26 27 28 29 30 LCP (39,27) (28,40) (32,32) (43,43)(29,44)(40,30)(47,37)(55,25)(39,29) (30,36) LHW 17:25 10:25 12:00 12:25 11:05 13:25 13:35 13:30 13:30 18:15 LSW 17:35 10:35 12:10 12:35 11:15 13:35 13:45 13:40 13:40 18:25 USW 17:55 10:55 12:30 12:55 11:35 13:55 14:05 14:00 14:00 18:45 UHW 18:05 11:05 12:40 13:05 11:45 14:05 14:15 14:10 14:10 18:55 NC 1 1 1 1 1 1 4 1 2 2
An Algorithm to Vehicle Scheduling Problem of AirPort Pickup and Delivery Service 88 , bc bb cc NN nsns (6) where b and c denote the number of the total cus tomers delivered by basic and collaborative vehicles, respectively, b, b N N n , c, and c n represent the trip number and seat number of basic and collaborative vehi cles, respectively. When not considering the collabora tion, and . 0 c N0 c Simulation results show that without collaborations, the total running mileage of vehicles is: 1051.4km and average utilization ratio of vehicle capacity 57.89%. Based on the results at the first stage, we perform the heuristic algorithm at the second stage. By optimizing the results at the first stage, we can obtain the collaborative information of collaborative vehicles. Simulation results indicate that with collaborations, the total vehicle mile age is 1008.5 km and average utilization ratio of vehicle capacity is 61.90%. n Here we, respectively, use the study cases with 10, 30, 50, 100, 150, 200, 400, 600, 800 and 1000 customer points to validate further the performance of our algo rithm. The depot coordinate is at point (35, 37), while airport coordinate is at point (50, 50). According to the distribution of the customer point locations, we discuss the two cases, namely customer points mainly distributed near the depot or airport. And the locations of all the customer points are randomly distributed in the circle whose center is the depot or airport with radi us by 20 km. For collaborations and noncollaborations, we obtain the vehicle total mileage, the average utilization ratio of basic vehicles, and average satisfaction degree of cus tomers for the different study case. From Figures 14, we can see that in contrast to collaborations, average satis faction degree of customers decrease a little after col laborating. However, Figures 14 also tell us that the 0100 200300 400 500 600 700 800 900 1000 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 2.2x 10 4 Number of customer points Tota l mileage (km) Customer points mainly distributed near the depot without collaboration with collaboration Figure 1. Total mileage with customer points mainly near the depot. 0100 200 300400 500 600 700 800 900100 0 0.4 0.8 1.2 1.6 2 2.4 2.8x 10 4 Number of customer points Customer points mainly distributed near the airport without collaboration with collaboration Figure 2. Total mileage with customer points mainly near the airport. 0100 200300 400 500 600 7008009001000 0.95 0.96 0.97 0.98 0.99 1 1.01 1.02 1.03 1.04 1.05 Number of customer points A vera ge satis faction degree of customers Customer points mainly distributed near the depot without collaboration with collabora tion Figure 3. Average satisfaction degree of customers with customer points mainly near the depot. 0100 200 300 400 500600 700 800 9001000 0.95 0.96 0.97 0.98 0.99 1 1.01 1.02 1.03 1.04 1.05 Number of customer points Average satisfaction degree of customers Customer points mainly distriuted near the airport without collaboration with collaboration Figure 4. Average satisfaction degree of customers with customer points mainly near the airport. Copyright © 2013 SciRes. IB
An Algorithm to Vehicle Scheduling Problem of AirPort Pickup and Delivery Service Copyright © 2013 SciRes. IB 89 total mileage with collaborations is much less than that without collaborations. And we also find that the reduced total mileage is up to 4%. This is what we expect. By the vehicle collaborations, the satisfaction degree of custom ers in the collaborative vehicles is to decrease. As a result, this is to affect the average satisfaction degree of cus tomers. The reduced mileage is mainly because the col laborative vehicles need not go to the airport. After using the heuristic algorithm at the second stage, although the average satisfaction degree of customers decreases a little, the total running mileage of vehicles is reduced. And thus the vehicle scheduling cost is also reduced. Hence, simulation results indicate that the algorithm proposed in this paper can be used for all the study cases. This tells us that the algorithm proposed in this paper is effective and feasible. 4. Conclusions This paper studies the two vehicle kinds’ collaborative problems of the pickup and delivery service. By intro ducing the vehicle collaborations, a twostage heuristic algorithm is proposed. Considering the collaborations between isolated customer points and basic vehicles, we make the basic vehicle picking up the customers at the multiple customer points collaborating with other basic vehicles. And the customers at the different customer points are put into the same basic vehicle as possible and then are picked up to the airport. In such a case, the av erage utilization ratio of vehicle capacity is improved. Moreover, simulation results that in the case of keeping the appropriate customers’ satisfaction degree; we can perform the better vehicle scheduling. As a result, the cost of the company can be significantly reduced. Future studies need to consider the actual situations, such as multiple trips, waiting time when transferring, global collaboration, and dynamic insertion customers. 5. Acknowledgements This work was supported in part by the National Natural Science Foundation of China (Nos. 71021061, 61273204), and the Fundamental Research Funds for the Central Universities (No. N090204001). The authors wish to thank the reviewers for their helpful comments. REFERENCES [1] P. Pop, I. Kara and A. Marc, “New Mathematical Models of the Generalized Vehicle Routing Problem and Exten sions,” Applied Mathematical Modelling, 2012, Vol. 36, No. 1, pp. 97107.doi:10.1016/j.apm.2011.05.037 [2] P. Belfiore and H. Yoshizaki, “Heuristic Methods for the Fleet Size and Mix Vehicle Routing Problem with Time Windows and Split Deliveries,” Computers and Industrial Engineering, Vol. 64, No. 2, 2013, pp. 589601. doi:10.1016/j.cie.2012.11.007 [3] D. Jiang and G. Hu, “GARCH Modelbased Largescale IP Traffic Matrix Estimation,” IEEE Communications Letters, Vol. 13, No. 1, 2009, pp. 5254. doi:10.1109/LCOMM.2008.081271 [4] D. Jiang and G. Hu, “An Accurate Approach to Largescale IP Traffic Matrix Estimation,” IEICE Trans actions on Communications, Vol. E92B, No. 1, 2009, pp. 322325. [5] J. Wy and B. Kim, “A Hybrid Metaheuristic Approach for the Rollon–rolloff Vehicle Routing Problem,” Computers and Operations Research, Vol. 40, No. 8, 2013, pp. 19471952.doi:10.1016/j.cor.2013.03.006 [6] D. Mester, O. Braysy and W. Dullaert, “A Multiparametric Evolution Strategies Algorithm for Ve hicle Routing Problems,” Expert Systems with Applica tions, Vol. 32, No. 2, 2007, pp. 508517. doi:10.1016/j.eswa.2005.12.014 [7] M. Rancourt, J. Cordeau and G. Laporte, “LongHaul Vehicle Routing and Scheduling with Working Hour Rules,” Transportation Science, Vol. 47, No. 1, 2013, pp. 81107.doi:10.1287/trsc.1120.0417 [8] S. Yan, S. Wang and M. Wu, “A Model with a Solution Algorithm for the Cash Transportation Vehicle Routing and Scheduling Proble,” Computers and Industrial Engi neering, Vol. 63, No. 2, 2012, pp. 464473. doi:10.1016/j.cie.2012.04.004 [9] Z. Xu and J. Tang, “A Coordinationbased Twostage Algorithm for Pickup and Delivery Customer to Airport Service,” in Proc. of ICMSEM’13, 2013, pp. 19.
