Adaptive large neighborhood search Algorithm for route planning of freight buses with pickup and delivery

Zheng Chang; Haoxun Chen; Farouk Yalaoui; Bo Dai

doi:10.3934/jimo.2020045

Article Contents

2021, Volume 17, Issue 4: 1771-1793. Doi: 10.3934/jimo.2020045

This issue Previous Article Genetic algorithm for obstacle location-allocation problems with customer priorities Next Article Network data envelopment analysis with fuzzy non-discretionary factors

Adaptive large neighborhood search Algorithm for route planning of freight buses with pickup and delivery

1.
Research Institute of Highway Ministry of Transport, Beijing 100070, China
2.
University of Technology of Troyes, TROYES 10004, France
3.
Hunan University of Technology and Business, ChangSha 410205, Hunan, China

^* Corresponding author: Haoxun Chen and Bo Dai
^* Corresponding author: Haoxun Chen and Bo Dai

Received: October 31, 2018

Revised: June 30, 2019

Early access: March 2020

Published: July 2021

Abstract Full Text(HTML) Figure(6) / Table(7) Related Papers Cited by

Abstract

Freight bus is a new public transportation means for city logistics, and each freight bus can deliver and pick up goods at each customer/supplier location it passes. In this paper, we study the route planning problem of freight buses in an urban distribution system. Since each freight bus makes a tour visiting a set of pickup/delivery locations once at every given time interval in each day following a fixed route, the route planning problem can be considered a new variant of periodic vehicle routing problem with pickup and delivery. In order to solve the problem, a Mixed-Integer Linear Programming (MILP) model is formulated and an Adaptive Large Neighborhood Search (ALNS) algorithm is developed. The development of our algorithm takes into consideration specific characteristics of this problem, such as fixed route for each freight bus, possibly serving a demand in a later period but with a late service penalty, etc. The relevance of the mathematical model and the effectiveness of the proposed ALNS algorithm are proved by numerical experiments.

Keywords:

Adaptive large neighborhood search Algorithm,
route planning,
freight bus,
joint distribution.

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

Citation:

Full Text(HTML)

Figure 1. City freighters in an urban distribution system

Download: Full-size image PowerPoint slide

Figure 2. Freight buses in an urban distribution system

Download: Full-size image PowerPoint slide

Figure 3. An example of freight bus lines

Download: Full-size image PowerPoint slide

Figure 4. The procedure framework of ALNS

Download: Full-size image PowerPoint slide

Figure 5. The average performances of CPLEX and ALNS ($ M = 3 $)

Download: Full-size image PowerPoint slide

Figure 6. The average performances of CPLEX and ALNS ($ M = 5 $)

Download: Full-size image PowerPoint slide

Table 3. Experimental results of small size instances

Instances	$ Cplex_{Obj} $	LB	$ ALNS_{Obj} $	$ Gap_{Cplex} $	$ Gap_{ALNS} $	$ Imp_{ALNS-Cplex} $	$ CPU_{Cplex} $	$ CPU_{ALNS} $
7-3a	1067.1	1067.1	1067.1	0.00	0.00	0.00	86.3	7.9
7-3b	986.6	986.6	986.6	0.00	0.00	0.00	89.6	7.6
7-3c	1076.9	1076.9	1076.9	0.00	0.00	0.00	87.9	8.2
7-3d	962.0	962.0	962.0	0.00	0.00	0.00	87.6	8.7
7-3e	1005.8	1005.8	1005.8	0.00	0.00	0.00	87.5	7.9
7-5a	1984.1	1984.1	1984.1	0.00	0.00	0.00	257.3	19.7
7-5b	1945.1	1945.1	1945.1	0.00	0.00	0.00	262.1	20.3
7-5c	1887.0	1887.0	1887.0	0.00	0.00	0.00	258.2	21.9
7-5d	1940.4	1940.4	1940.4	0.00	0.00	0.00	259.3	19.8
7-5e	1896.6	1896.6	1896.6	0.00	0.00	0.00	260.3	20.3
13-3a	1459.9	1074.8	1197.0	35.83	11.37	18.01	3600	25.8
13-3b	1519.1	1089.3	1207.8	39.46	10.88	20.49	3600	25.6
13-3c	1800.1	1342.1	1530.6	34.13	14.05	14.97	3600	26.9
13-3d	1397.4	1007.7	1123.6	38.67	11.50	19.59	3600	26.3
13-3e	2878.7	1848.4	2086.5	55.74	12.88	27.52	3600	27.1
13-5a	3761.2	2527.9	2847.0	48.79	12.62	24.30	3600	40.3
13-5b	3232.8	2264.2	2673.5	42.78	18.08	17.30	3600	39.7
13-5c	3329.6	2220.5	2607.1	49.95	17.41	21.70	3600	42.3
13-5d	3402.7	2238.7	2581.8	51.99	15.33	24.13	3600	41.2
13-5e	3405.6	2427.8	2856.6	40.28	17.66	16.12	3600	40.3

| Show Table

DownLoad: CSV

Table 1. Parameter Setting of the ALNS for different sizes of instances

Parameter	Small instances	Medium instances	Large instances
Maximum iterations number of ALNS $ (N) $	25000	30000	35000
The roulette parameter $ (r) $	0.1	0.1	0.1
The score increment of generating a new best solution (Q1)	5	5	5
The score increment of generating a better solution (Q2)	3	3	3
The score increment of generating a worse solution (Q3)	1	1	1
Initial temperature parameter $ \left(P_{\text {init}}\right) $	100	120	120
Cooling rate $ (\mathrm{h}) $	0.992	0.994	0.996
Removal fraction $ (\rho) $	0.2	0.2	0.3
Noise parameter $ (\mathrm{u}) $	0.1	0.1	0.1

| Show Table

DownLoad: CSV

Table 2. Performance indicators

Abbreviation	Definition
$ Cplex_{Obj} $	The best feasible objective value found by CPLEX in a preset running time
LB	The lower bound produced by CPLEX in a preset running time
$ ALNS_{Obj} $	The best feasible objective value obtained by ALNS after a preset number of iterations
$ Gap_{Cplex} $	The gap between $ Cplex_{Obj} $ and LB, which is defined as ($ Cplex_{Obj} $- LB)/LB*100
$ Gap_{ALNS} $	The gap between $ ALNS_{Obj} $ and LB, which is defined as ($ ALNS_{Obj} $- LB)/ LB*100
$ Imp_{ALNS-Cplex} $	The improvement (reduction) of $ ALNS_{Obj} $ over $ Cplex_{Obj} $, which is defined as ($ Cplex_{Obj} $- $ ALNS_{Obj} $)/ $ Cplex_{Obj} $*100
$ CPU_{Cplex} $	The CPU time (second) of CPLEX
$ CPU_{ALNS} $	The CPU time (second) of ALNS

| Show Table

DownLoad: CSV

Table 4. Experimental results of medium size instances

Instances	$ Cplex_{Obj} $	LB	$ ALNS_{Obj} $	$ Gap_{Cplex} $	$ Gap_{ALNS} $	$ Imp_{ALNS-Cplex} $	$ CPU_{Cplex} $	$ CPU_{ALNS} $
20-3a	2884.5	1966.6	2161.4	46.67	9.91	25.07	5400	135.7
20-3b	3014.2	2101.2	2251.3	43.45	7.14	25.31	5400	140.7
20-3c	3058.2	2069.5	2268.2	47.77	9.60	25.83	5400	133.2
20-3d	2649.0	1807.7	2013.2	46.54	11.37	24.00	5400	135.7
20-3e	2904.7	1949.3	2141.2	49.01	9.84	26.29	5400	134.2
20-5a	5161.4	2951.8	3365.4	74.86	14.01	34.80	5400	216.4
20-5b	4527.3	2627.2	2992.6	72.32	13.91	33.90	5400	203.5
20-5c	4758.4	2698.5	3065.1	76.34	13.59	35.59	5400	218.8
20-5d	4474.2	2556.1	2852.5	75.04	11.60	36.25	5400	199.5
20-5e	4522.8	2573.0	2927.5	75.78	13.78	35.27	5400	220.3
30-3a	4964.2	2664.8	3003.9	86.29	12.73	39.49	7200	289.3
30-3b	5401.6	2922.8	3321.7	84.81	13.65	38.50	7200	276.8
30-3c	4688.7	2520.6	2860.1	86.02	13.47	39.00	7200	296.3
30-3d	4540.4	2381.9	2728.1	90.62	14.53	39.92	7200	295.3
30-3e	4654.2	2502.6	2844.2	85.97	13.65	38.89	7200	287.6
30-5a	-	4325.6	5167.3	-	19.46	-	7200	356.7
30-5b	8140.4	4084.0	4859.6	99.32	18.99	40.30	7200	320.7
30-5c	-	4390.0	5249.4	-	19.58	-	7200	364.3
30-5d	-	3973.0	4733.7	-	19.15	-	7200	378.9
30-5e	-	4154.9	4938.6	-	18.86	-	7200	352.1
40-3a	6214.3	2835.6	3371.3	119.15	18.89	45.75	10800	478.7
40-3b	6389.9	2832.7	3372.6	125.58	19.06	47.22	10800	480.3
40-3c	-	2917.5	3469.4	-	18.92	-	10800	437.9
40-3d	6072.1	2832.0	3381.9	114.41	19.42	44.30	10800	509.3
40-3e	6112.3	3008.5	3590.5	103.17	19.35	41.26	10800	469.5
40-5a	-	4824.4	6020.8	-	24.80	-	10800	597.3
40-5b	-	5065.7	6325.8	-	24.88	-	10800	600.1
40-5c	-	4944.1	6088.1	-	23.14	-	10800	623.5
40-5d	-	4823.4	5940.9	-	23.17	-	10800	591.2
40-5e	-	4664.0	5764.5	-	23.60	-	10800	589.7

| Show Table

DownLoad: CSV

Table 5. Experimental results of large size instances

Instances	$ Cplex_{Obj} $	LB	$ ALNS_{Obj} $	$ Gap_{Cplex} $	$ Gap_{ALNS} $	$ Imp_{ALNS-Cplex} $	$ CPU_{Cplex} $	$ CPU_{ALNS} $
60-3a	11510.5	4550.1	5313.7	152.97	16.78	53.84	14400	979.3
60-3b	-	5140.4	5971.6	-	16.17	-	14400	1000.1
60-3c	11918.4	4742.3	5507.3	151.32	16.13	53.79	14400	1005.3
60-3d	-	4340.2	5106.7	-	17.66	-	14400	989.3
60-3e	11509.7	4694.8	5494.9	145.16	17.04	52.26	14400	996.1
60-5a	-	8123.9	9972.9	-	22.76	-	14400	1421.6
60-5b	-	7669.4	9493.1	-	23.78	-	14400	1432.3
60-5c	-	8041.2	9809.9	-	22.00	-	14400	1410.5
60-5d	-	8318.1	10172.5	-	22.29	-	14400	1396.3
60-5e	-	8372.7	10135.2	-	21.05	-	14400	1389.3
80-3a	-	6288.6	7419.3	-	17.98	-	18000	1523.4
80-3b	-	5992.0	7135.8	-	19.09	-	18000	1612.3
80-3c	-	6431.5	7683.1	-	19.46	-	18000	1496.8
80-3d	-	5785.2	6836.7	-	18.18	-	18000	1527.4
80-3e	-	6104.0	7264.1	-	19.01	-	18000	1559.3
80-5a	-	8670.0	10889.2	-	25.60	-	18000	1963.2
80-5b	-	8260.9	10207.5	-	23.56	-	18000	2001.3
80-5c	-	8855.8	11163.3	-	26.06	-	18000	1989.7
80-5d	-	8611.5	10627.6	-	23.41	-	18000	1967.3
80-5e	-	8596.7	10703.1	-	24.50	-	18000	1995.3

| Show Table

DownLoad: CSV

Table 6. The average performances of the two solution methods

Instances	$ Gap_{Cplex} $	$ Gap_{ALNS} $	$ Imp_{ALNS-Cplex} $	$ CPU_{Cplex} $	$ CPU_{ALNS} $
7-3	0	0	0	87.78	8.06
7-5	0	0	0	259.44	20.4
13-3	40.76	12.14	20.12	3600	26.3
13-5	46.76	16.22	20.71	3600	40.76
20-3	46.69	9.57	25.30	5400	135.9
20-5	74.87	13.38	35.16	5400	211.7
30-3	86.74	13.61	39.16	7200	289.1
30-5	99.32	19.21	40.30	7200	354.5
40-3	115.58	19.13	44.63	10800	475.1
40-5	-	23.92	-	10800	600.4
60-3	149.82	16.76	53.30	14400	994.0
60-5	-	22.38	-	14400	1410.0
80-3	-	18.74	-	18000	1543.8
80-5	-	24.63	-	18000	1983.4

| Show Table

DownLoad: CSV

Table 7. The comparison of the average costs of the two systems

	Instances	System without Freight bus	System with Freight bus	Cost Saving in percentage
Small size instances	7-3	1237.50	1019.7	17.6
	7-5	2363.04	1930.6	18.3
	13-3	1779.70	1429.1	19.7
	13-5	3400.00	2713.2	20.2
Medium size instances	20-3	2818.08	2167.1	23.1
	20-5	3938.60	3040.6	22.8
	30-3	3909.40	2951.6	24.5
	30-5	6635.24	4989.7	24.8
	40-3	4625.98	3437.1	25.7
	40-5	8168.02	6028	26.2
Large size instances	60-3	7749.36	5478.8	29.3
	60-5	14186.98	9916.7	30.1
	80-3	10945.48	7267.8	33.6
	80-5	16565.84	10718.1	35.3

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	D. Aksen, O. Kaya, F. S. Salman and Ö. Tuncel, An adaptive large neighbor- hood search algorithm for a selective and periodic inventory routing problem, European Journal of Operational Research, 239 (2014), 413-426. doi: 10.1016/j.ejor.2014.05.043.
[2]	E. J. Beltrami and L. D. Bodin, Networks and vehicle routing for municipal waste collection, Networks, 4 (1974), 65-94. doi: 10.1002/net.3230040106.
[3]	R. Bent and P. V. Hentenryck, A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows, Computers & Operations Research, 33 (2006), 875-893.
[4]	N. Christofides and J. E. Beasley, The period routing problem, Networks, 14 (1984), 237-256.
[5]	A. M. Campbell and H. W. Jill, Forty years of periodic vehicle routing, Networks, 63 (2014), 2-15. doi: 10.1002/net.21527.
[6]	I.-M. Chao, B. L. Golden and E. Wasil, An improved heuristic for the period vehicle-routing problem, Networks, 26 (1995), 25-44. doi: 10.1002/net.3230260104.
[7]	Z. Chang and H. Chen, Freight buses in three-tiered distribution systems for city logistics: Modeling and evaluation, 7th IESM Conference, (2017).
[8]	J. F. Cordeau, M. Gendreau and G. Laporte, A guide to vehicle routing heuristics, Journal of the Operational Research Society, 53 (2002), 512-522.
[9]	G. Clarke and J. W. Wright, Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, 12 (1964), 568-581. doi: 10.1007/978-3-642-27922-5_18.
[10]	B. Dai and H. X. Chen, Proportional egalitarian core solution for profit allocation games with an application to collaborative transportation planning, European Journal of Industrial Engineering, 9 (2015), 53-76. doi: 10.1504/EJIE.2015.067456.
[11]	L. M. A. Drummond, L. S. Ochi and D. S. Vianna, An asynchronous parallel metaheuristic for the period vehicle routing problem, Future Generation Computer System, 17 (2001), 379-386. doi: 10.1016/S0167-739X(99)00118-1.
[12]	E. Demir, T. Bektas and G. Laporte, An adaptive large neighborhood search heuristic for the Pollution-Routing Problem, European Journal of Operational Research, 223 (2012), 346-359. doi: 10.1016/j.ejor.2012.06.044.
[13]	B. Dai, H. X. Chen and G. K. Yang, Price-setting based combinatorial auction approach for carrier collaboration with pickup and delivery requests, Operational Research, 14 (2014), 361-386. doi: 10.1007/s12351-014-0141-1.
[14]	P. Francis, K. Smilowitz and M. Tzur, The period vehicle routing problem with service choice, Transportation Science, 40 (2006), 439-454. doi: 10.1287/trsc.1050.0140.
[15]	L. E. Gill and R. P. Allerheiligen, Co-operation in channels of distribution: Physical distribution leads the way, International Journal of Physical Distribution & Logistics Management, 26 (1996), 49-63. doi: 10.1108/eb014521.
[16]	M. Gaudioso and G. Paletta, A heuristic for the periodic vehicle routing problem, Transport Science, 26 (1992), 86-92. doi: 10.1287/trsc.26.2.86.
[17]	D. Goeke and M. Schneider, Routing a mixed fleet of electric and conventional vehicles, European Journal of Operational Research, 245 (2015), 81-99. doi: 10.1016/j.ejor.2015.01.049.
[18]	Y. Hao and Y. Su, The research on joint distribution mode of the chain retail enterprises, International Conference on Mechatronics, Electronic, Industrial and Control Engineering, MEIC, (2014), 1694–1697.
[19]	M. Y. Lai, H. M. Yang, S. P. Yang, J. H. Zhao and Y. Xu, Cyber-physical logistics system-based vehicle routing optimization, Journal of Industrial and Management Optimization, 10 (2014), 701-715. doi: 10.3934/jimo.2014.10.701.
[20]	L. L. Lv, Z. Zhang, L. Zhang and W. S. Wang, An iterative algorithm for periodic Sylvester matrix equations, Journal of Industrial and Management Optimization, 14 (2018), 413-425. doi: 10.3934/jimo.2017053.
[21]	N. Labadie, R. Mansini, J. Melechovský and R. Wolfler-Calvo, The team orienteering problem with time windows: An LP-based granular variable neighborhood search, European Journal of Operational Research, 220 (2012), 15-27. doi: 10.1016/j.ejor.2012.01.030.
[22]	Y. Li, H. X. Chen and C. Prins, Adaptive large neighborhood search for the pickup and delivery problem with time windows, profits, and reserved requests, European Journal of Operational Research, 252 (2016), 27-38. doi: 10.1016/j.ejor.2015.12.032.
[23]	S. Majidi, S. M. Hosseini-Motlagh and J. Ignatius, Adaptive large neighborhood search heuristic for pollution-routing problem with simultaneous pickup and delivery, Soft Computing, 22 (2018), 2851-2865. doi: 10.1007/s00500-017-2535-5.
[24]	A. C. Matos and R. C. Oliverira, An experimental study of the ant colony system for the period vehicle routing problem, Lecture Notes in Computer Science, 3172 (2004), 286-293. doi: 10.1007/978-3-540-28646-2_26.
[25]	A. R. Pourghaderi, R. Tavakkoli-Moghaddam, M. Alinaghian and B. Beheshti-Pour, A simple and effective heuristic for periodic vehicle routing problem, Proceedings of the 2008 IEEE International Conference on Industrial Engineering Management, (2008), 133–137. doi: 10.1109/IEEM.2008.4737846.
[26]	D. Pisinger and S. Ropker, A general heuristic for vehicle routing problems, Computers and Operations Research, 34 (2007), 2403-2435. doi: 10.1016/j.cor.2005.09.012.
[27]	R. Russell and W. Igo, An assignment routing problem, Networks, 9 (1979), 1-17. doi: 10.1002/net.3230090102.
[28]	S. Roker and D. Pisinger, An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transportation Science, 40 (2006), 455-472.
[29]	I. Roozbeh, M. Ozlen and J. W. Hearne, An Adaptive Large Neighborhood Search for asset protection during escaped wildfires, Computers and Operations Research, 97 (2018), 125-134. doi: 10.1016/j.cor.2018.05.002.
[30]	X. Shize, Introductions of joint distribution, Circulation and economic study, 8 (1973), 87-94.
[31]	P. Shaw, Using constraint programming and local search methods to solve vehicle routingproblems, Proceedings of the 4th International Conference on Principles and Practice of Constraint Programming Springer New York, (1998), 417–431.
[32]	A. Trentini, A. Campi, N. Malhene and F. Boscacci, Shared passengers & goods urban transport solutions: New ideas for milan through en international comparison, Territorio, 59 (2011), 38-44.
[33]	L. Verdonck, A. Caris, K. Ramaekers and G. K. Janssens, Collaborative logistics from the perspective of road transportation companies, Transport Reviews, 33 (2013), 700-719. doi: 10.1080/01441647.2013.853706.
[34]	L. Xu and D. Yang, Research on joint distribution cost allocation model, Boletin Tecnico/Technical Bulletin, 55 (2017), 291-297.
[35]	N. Yalaoui, L. Amodeo, F. Yalaoui and H. Mahdi, Efficient methods to schedule reentrant flow shop system, Journal of Intelligent and Fuzzy Systems, 26 (2014), 1113-1121. doi: 10.3233/IFS-130771.
[36]	S. Zhou, Logistics bottleneck of online retail industry in China, Journal of Supply Chain and Operations Management, 11 (2013), 1-11.