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

苏兵, WyattCarlson, 范佳彬, GAO Arthur, 邵艳君, 林国辉

Sharing bicycle relocating with minimum carbon emission

Bing SU, Wyatt CARLSON, Jiabin FAN, Arthur GAO, Yanjun SHAO, Guohui LIN

Table 1 The performance of all three algorithms IQP-Cplex, Greedy and TSP-based on the $ 100 $ simulated instances for the $ n $-station datasets, where $ n \in \{16, 17, \cdots, 20\} $. In this experiment, a light truck is dispatched with its capacity $ Q = 15 $ and its own weight ignored. Rows 3–5 (6–8, respectively) contain the average carbon emissions (average travel distances, respectively) and their standard deviations over the $ 100 $ instances, in the solutions by the three algorithms.The last row records the average running times of IQP-Cplex and the standard deviations

#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