Operations Research Transactions >
2022 , Vol. 26 >Issue 3: 75 - 91
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2022.03.006
Sharing bicycle relocating with minimum carbon emission
Received date: 2022-01-08
Online published: 2022-09-07
Supported by
National Social Science Foundation of China(20XGL023)
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.
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 . DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.006
| 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. |
| 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. |
| 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. |
| 6 | Anily S , Hassin R . The swapping problem[J]. Networks, 1992, 22, 419- 433. |
| 7 | Chalasani P , Motwani R . Approximating capacitated routing and delivery problems[J]. SIAM Journal on Computing, 1999, 28, 2133- 2149. |
| 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. |
| 14 | Goldberg A V , Karzanov A V . Maximum skew-symmetric flows and matchings[J]. Mathematical Programming, 2004, 100, 537- 568. |
/
| 〈 |
|
〉 |
