最小化碳排放的共享单车迁移问题

doi:10.15960/j.cnki.issn.1007-6093.2022.03.006

Abstract

Abstract:

We formulate the sharing bicycle relocating practice as a novel optimization problem, which can be regarded as a variant of the classic TSP problem while its objective function is no longer the length of the Hamiltonian tour but the carbon emission. A well-adopted carbon emission formula that is the product of the load of the vehicle and the travel distance is employed and we propose two heuristic algorithms Greedy and TSP-based, inside both of which we set the priority to reduce the load of the vehicle for minimizing carbon emission. The feasibility of both algorithms is proven and numerical experiments are conducted to validate their performance empirically. The promise of Greedy over TSP-based algorithm is shown to the sharing bicycle companies for their daily dispatching practice.

Key words: sharing bicycle, carbon emission, integer quadratic program, traveling salesman problem, heuristics, Cplex

CLC Number:

O221.2

Bing SU, Wyatt CARLSON, Jiabin FAN, Arthur GAO, Yanjun SHAO, Guohui LIN. Sharing bicycle relocating with minimum carbon emission[J]. Operations Research Transactions, 2022, 26(3): 75-91.

Figures/Tables 7

References 14

1	Benchimol M , Benchimol P , Chappert B , de la Taille A , Laroche F , Meunier F , Robinet L . Balancing the stations of a self service bike hire system[J]. RAIRO Operations Research, 2011, 45, 37- 61. doi: 10.1051/ro/2011102
2	Toro E M , Franco J F , Echeverri M G , et al. Green open location-routing problem considering economic and environmental costs[J]. International Journal of Industrial Engineering Computations, 2017, 8 (2): 203- 216.
3	Dell'Amico M , Hadjicostantinou E , Iori M , et al. The bike sharing rebalancing problem: Mathematical formulations and benchmark instances[J]. Omega, 2014, 45, 7- 19. doi: 10.1016/j.omega.2013.12.001
4	Rainer-Harbach M, Papazek P, Hu B, and Raidl G R. Balancing bicycle sharing systems: A variable neighborhood search approach[C]//Proceedings of the 2013 Evolutionary Computation in Combinatorial Optimization, LNCS 7832, 2013: 121-132.
5	Gaspero L D , Rendl A , Urli T . Balancing bike sharing systems with constraint programming[J]. Constraints, 2016, 21, 318- 348. doi: 10.1007/s10601-015-9182-1
6	Anily S , Hassin R . The swapping problem[J]. Networks, 1992, 22, 419- 433. doi: 10.1002/net.3230220408
7	Chalasani P , Motwani R . Approximating capacitated routing and delivery problems[J]. SIAM Journal on Computing, 1999, 28, 2133- 2149. doi: 10.1137/S0097539795295468
8	Charikar M, Khuller S, and Raghavachari B. Algorithms for capacitated vehicle routing[C]// Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC'98), 1998: 349-358.
9	Peng Y, Wang X. Research on a vehicle routing schedule to reduce fuel consumption[C]//Proceedings of the 2009 IEEE International Conference on Measuring Technology and Mechatronics Automation, 2009: 825-827.
10	Scott C, Urquhart N, Hart E. Influence of topology and payload on CO$_2$ optimised vehicle routing[C]//Proceedings of EvoApplications 2010, Part Ⅱ, LNCS 6025, 2010, 141-150.
11	Palmer A. The development of an integrated routing and carbon dioxide emissions model for goods vehicles[D]. Bedford: Cranfield University, 2007.
12	Christofides N. Worst-case analysis of a new heuristic for the travelling salesman problem[R]. Graduate School of Industrial Administration, Carnegie Mellon University, 1976.
13	Min H . The multiple vehicle routing problems with simultaneous delivery and pickup points[J]. Transportation Research, 1989, 23, 377- 386. doi: 10.1016/0191-2607(89)90085-X
14	Goldberg A V , Karzanov A V . Maximum skew-symmetric flows and matchings[J]. Mathematical Programming, 2004, 100, 537- 568.

#Stations	$ 16 $	$ 17 $	$ 18 $	$ 19 $	$ 20 $
Christofides' distance	46.76	46.84	44.26	45.47	46.69
IQP-Cplex emission	110.75$ \pm $18.31	110.87$ \pm $21.79	121.26$ \pm $22.83	119.07$ \pm $19.61	121.63$ \pm $19.01
Greedy emission	188.37$ \pm $44.09	189.04$ \pm $43.75	213.50$ \pm $51.24	220.65$ \pm $55.84	218.74$ \pm $51.07
TSP-based emission	229.75$ \pm $52.15	255.32$ \pm $69.64	258.47$ \pm $64.29	252.58$ \pm $60.50	256.84$ \pm $58.52
IQP-Cplex distance	50.81$ \pm $5.41	52.43$ \pm $4.94	59.23$ \pm $5.79	59.22$ \pm $6.57	61.04$ \pm $6.20
Greedy distance	49.91$ \pm $6.15	51.40$ \pm $5.63	57.25$ \pm $6.46	58.75$ \pm $6.77	59.97$ \pm $6.52
TSP-based distance	58.43$ \pm $7.09	63.92$ \pm $7.61	66.59$ \pm $9.05	66.50$ \pm $9.82	68.54$ \pm $8.82
IQP-Cplex time (seconds)	12.68$ \pm36.90 $	81.15$ \pm $176.65	1 673.73$ \pm $5 331.30	2 028.63$ \pm $5 685.02	3 756.00$ \pm $8 362.41

	$ Q/a_0 $	25-station	won	110-station	won
Christofides' distance		54.99		175.52
Greedy emission	15/0	272.03$ \pm $56.89	82	686.39$ \pm $98.45	99
TSP-based emission		342.90$ \pm $72.79	18	1 099.99$ \pm $206.38	1
Greedy distance		73.23$ \pm $7.38	87	192.13$ \pm $20.45	99
TSP-based distance		88.29$ \pm $11.81	13	291.31$ \pm $38.37	1
Greedy emission	25/10	1 199.28$ \pm $161.65	82	3 129.66$ \pm $295.90	100
TSP-based emission		1 428.43$ \pm $222.73	18	4 719.92$ \pm $578.61	0
Greedy distance		74.42$ \pm $8.11	84	194.47$ \pm $15.73	100
TSP-based distance		86.43$ \pm $12.26	16	287.97$ \pm $31.36	0
Greedy emission	50/20	2 383.08$ \pm $326.58	89	6 367.98$ \pm $555.97	100
TSP-based emission		2 911.67$ \pm $419.40	11	9 568.11$ \pm $1 327.58	0
Greedy distance		73.18$ \pm $8.26	89	196.91$ \pm $15.80	100
TSP-based distance		86.51$ \pm $10.80	11	285.32$ \pm $36.45	0

	$ Q(a_0 + \mbox{#bicycles}) $	25-station	won	110-station	won
Greedy emission	15(0+5)	303.65$ \pm $68.93	83	730.16$ \pm $108.21	100
TSP-based emission		394.12$ \pm $78.14	17	1 180.03$ \pm $213.49	0
Greedy distance		72.28$ \pm $7.24	93	192.07$ \pm $20.12	100
TSP-based distance		91.31$ \pm $11.73	7	292.48$ \pm $41.24	0
Greedy emission	15(0+10)	355.52$ \pm $90.61	81	763.26$ \pm $118.17	99
TSP-based emission		453.38$ \pm $73.05	19	1 255.51$ \pm $214.03	1
Greedy distance		71.91$ \pm $7.55	94	190.68$ \pm $19.45	99
TSP-based distance		93.09$ \pm $11.56	6	293.69$ \pm $39.23	1
Greedy emission	25(10+5)	1 231.78$ \pm $175.21	82	3 162.01$ \pm $309.60	100
TSP-based emission		1 501.64$ \pm $220.49	18	4 835.77$ \pm $569.09	0
Greedy distance		73.99$ \pm $8.32	84	194.57$ \pm $16.52	100
TSP-based distance		87.63$ \pm $11.87	16	289.05$ \pm $30.53	0
Greedy emission	25(10+10)	1 245.23$ \pm $165.22	86	3 199.52$ \pm $277.91	100
TSP-based emission		1 541.14$ \pm $225.77	14	4 936.85$ \pm $623.24	0
Greedy distance		72.46$ \pm $7.61	90	193.88$ \pm $14.94	100
TSP-based distance		88.13$ \pm $11.31	10	290.35$ \pm $33.19	0
Greedy emission	50(20+5)	2 411.84$ \pm $333.12	91	6 409.37$ \pm $588.91	100
TSP-based emission		2 993.68$ \pm $435.39	9	9 808.92$ \pm $1382.58	0
Greedy distance		73.33$ \pm $8.81	89	196.74$ \pm $16.60	100
TSP-based distance		87.54$ \pm $11.34	11	287.73$ \pm $38.43	0
Greedy emission	50(20+10)	2 476.63$ \pm $356.19	92	6 417.28$ \pm $614.07	100
TSP-based emission		3 057.94$ \pm $442.25	8	9 794.56$ \pm $1386.81	0
Greedy distance		74.01$ \pm $9.34	88	195.71$ \pm $16.47	100
TSP-based distance		87.56$ \pm $12.13	12	285.04$ \pm $37.42	0

	$ Q $	$ 110 $-station	won
Greedy emission	1	83.86$ \pm $11.63	100
TSP-based emission		149.53$ \pm $25.99	0
Greedy distance		169.80$ \pm $21.78	100
TSP-based distance		311.11$ \pm $46.25	0
Greedy emission	2	82.15$ \pm $12.62	100
TSP-based emission		154.12$ \pm $27.63	0
Greedy distance		166.53$ \pm $24.24	100
TSP-based distance		319.41$ \pm $50.31	0
Greedy emission	4	85.99$ \pm $12.44	100
TSP-based emission		155.01$ \pm $26.10	0
Greedy distance		166.15$ \pm $21.44	100
TSP-based distance		313.98$ \pm $42.46	0
Greedy emission	8	101.12$ \pm $29.84	95
TSP-based emission		176.22$ \pm $41.87	5
Greedy distance		162.42$ \pm $20.13	100
TSP-based distance		313.76$ \pm $48.69	0

[1]	Xiaoguang BAO, Chao LU, Dongmei HUANG, Wei YU. Approximation algorithm for min-max cycle cover problem on a mixed graph [J]. Operations Research Transactions, 2021, 25(1): 107-113.
[2]	ZHANG Yuzhong, YANG Xiaoguang. The continuity properties of optimal value function of discrete optimization problems [J]. Operations Research Transactions, 2016, 20(3): 79-84.

Sharing bicycle relocating with minimum carbon emission

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 7

References 14

Related Articles 2

Recommended Articles

Metrics

Comments