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

Sharing bicycle relocating with minimum carbon emission

作　　者：苏兵[1] Wyatt Carlson 范佳彬 GAO Arthur 邵艳君 林国辉 SU Bing;CARLSON Wyatt;FAN Jiabin;GAO Arthur;SHAO Yanjun;LIN Guohui(School of Economics and Management,Xi'an Technological University,Xi'an 710021,Shaanxi,China;Department of Computing Science,University of Alberta,Edmonton,T6G 2E8 Alberta,Canada)

机构地区：[1]西安工业大学经济管理学院,陕西西安710021 [2]阿尔伯塔大学计算科学系,加拿大阿尔伯塔埃德蒙顿T6G 2E8

出　　处：《运筹学学报》2022年第3期75-91,共17页Operations Research Transactions

基　　金：National Social Science Foundation of China(No.20XGL023)。

摘　　要：本文考虑共享单车迁移问题,它可看作是经典旅行售货商问题的一个新颖变形,不同的是其目标函数为最小化碳排放。其中,碳排放利用单车负载与其行驶路程的乘积进行刻画。我们提出了两个启发式算法:贪心和基于TSP的算法,每个算法的核心思想均是优先减少单车负载。从理论上证明算法的可行性并给出数据实验以验证算法的实际性能。数据实验结果表明贪心算法优于基于TSP的算法,这为共享单车企业进行日常单车分配提供了理论依据。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.

关 键 词：共享单车 碳排放 整数二次规划 旅行售货商问题 启发式算法 Cplex 

分 类 号：O221.2[理学—运筹学与控制论]