本文研究协同运输的路线整合问题(CTRIP):允许所有的O-D流(运输任务)在规定的路线长度内任意采取直通运输、单点中转、两点中转的整合运输路线,整合运输的中枢路段在支付固定成本后可产生运费折扣,如何选择O-D流的整合路线使得总成本最小? CTRIP广泛应用于航空、物流、快递等领域的整合运输实践。论文构造了CTRIP的混合整数规划模型和Benders分解算法,实验显示,算法表现出非常好的计算绩效。最后,我们利用一个具体实例对CTRIP与已有研究展开了比较,结论显示CTRIP更能保证中枢路段的规模优势 。
Collaborative transportation is a good way of saving logistics costs by integrating all transportation demands and transportation resources to achieve economies of scale. Under the scale effect, the unit transport cost is lower if we construct a hub arc by paying a fixed charge and take more flow to the arc. And transportation tasks have to carefully choose their route since zigzag route has larger distance than direct route. In this paper, collaborative transportation routing integration problem are studied with fixed arc costs and distance limitation(CTRIP), which seeks the optimal transportation route of all O-D flow to minimize the total costs including routing costs of tasks and fixed costs of hub arcs, while the routing distance is required to be within a limited range. CTRIP arises in the application on airline transportation, road transportation, postal services and pipeline transport. A mixed-integer programming model is formulated for CTRIP, and a heuristic algorithm is provided based on Benders Decomposition. Then, a computational experiment is carried out based on AP data set from OR-Library, and the results show the algorithm works well. Further, CTRIP is compared with current relative researches about Hub-and-Spoke Network Design Problem (HASNDP) on a special instance. It is found that CTRIP can better guarantee scale advantages of hub arcs than CTRIP which has a flaw hypothesis.Unlike HASNDP which concentrate on integrating tasks through hubs, combing transport through hub arcs is the focus of this paper. The study can provide a new perspective research about collaborative transportation by shifting our method from integrating tasks through nodes to combing transport through arcs.
[1] Filipovic V, Kratica J, Tosic D, et al. GA inspired heuristic for uncapacitated single allocation hub location problem[J]. Applications of Soft Computing, 2009, 58:149-158.
[2] Koksalan M, Soylu B. Bicriteria p-hub location problems and evolutionary algorithms[J]. Informs Journal on Computing, 2010,22(4): 528-542.
[3] 翁克瑞. 轴辐式物流网络设计的选址与路线优化研究[M]. 成都:电子科技大学出版社, 2009.
[4] Campbell J F. Integer programming formulations of discrete hub location problems[J]. European Journal of Operational Research, 1994, 72(2): 387-405.
[5] Rodríguez-Martín I, Salazar-González J J. A local branching heuristic for the capacitated fixed-charge network design problem[J]. Computers & Operations Research, 2010, 37(3): 575-581.
[6] Randall M. Solution approaches for the capacitated single allocation hub location problem using ant colony optimisation[J]. Computational Optimization and Applications, 2008, 39(2): 239-261.
[7] Contreras I, Diaz J A, Fernandez E. Lagrangean relaxation for the capacitated hub location problem with single assignment[J]. Or Spectrum, 2009, 31(3): 483-505.
[8] Correia I, Nickel S, Saldanha-da-Gama F. The capacitated single-allocation hub location problem revisited: A note on a classical formulation[J]. European Journal Of Operational Research, 2010, 207(1): 92-96.
[9] Correia I, Nickel S, Saldanha-da-Gama F. Single-assignment hub location problems with multiple capacity levels[J]. Transportation Research Part B-Methodological, 2010, 4: 1047-1066.
[10] Puerto J, Ramos A B, Rodriguez-Chia A M. Single-allocation ordered median hub location problems[J]. Computers & Operations Research, 2011, 38(2): 559-570.
[11] Chen J F. The uncapacitated hub location problem with allocation constraints[C]. Proceedings of the Eighth International Conference on Information and Management Sciences:Series of Information and Management Sciences,Kunming,July 20-28,2009.
[12] Eiselt H A, Marianov V. A conditional p-hub location problem with attraction functions[J]. Computers & Operations Research, 2009, 36(12): 3128-3135.
[13] Campbell J F, Ernst A T, Krishnamoorthy M. Hub arc location problems: Part I-Introduction and results[J]. Management Science, 2005, 51: 1540-1555.
[14] Campbell J F, Ernst A T, Krishnamoorthy M. Hub Arc location problems: Part II - Formulations and optimal algorithms[J]. Management Science, 2005, 51: 1556-71.
[15] Campbell J F. Hub location for time definite transportation[J]. Computers & Operations Research, 2009, 36(12): 3107-3116.
[16] Camargo R S, Miranda J R G, Luna H P. Benders decomposition for hub location problems with economies of scale[J]. Transportation Science, 2009, 43(1): 86-97.
[17] 刘建国. 多经销商竞争的整车物流联合运输策略[J]. 中国管理科学,2011,19(5):38-63.
