交通运输系统工程与信息
交通運輸繫統工程與信息
교통운수계통공정여신식
JOURNAL OF COMMUNICATION AND TRANSPORTATION SYSTEMS ENGINEERING AND INFORMATION
2014年
5期
105-109,139
,共6页
铁路运输%取送车作业%破圈连接法%树枝形专用线%哈密尔顿图
鐵路運輸%取送車作業%破圈連接法%樹枝形專用線%哈密爾頓圖
철로운수%취송차작업%파권련접법%수지형전용선%합밀이돈도
railway transportation%placing-in and taking-out wagons%broken-circle and connection method%branch-shaped siding%Hamilton graph
合理安排铁路专用线取送车顺序,对提高调车机车作业效率、加速货车周转具有重要的意义。在已知条件下,以机车在装卸点间走行时间为权,把树枝形专用线取(送)车作业优化问题转换成哈密尔顿图最短路问题,并松弛为指派问题,采用匈牙利算法求出指派问题的最优解,可得到最短回路路长的下界或最优解。若未得到最优解,再利用破圈连接法求出满意的取(送)车顺序,此算法的复杂度为O(n2)。同时对送兼调移、取兼调移、取送结合、送调取结合作业形式进行了深入地讨论。最后举例说明了模型的构造及求解过程。大量小规模案例表明,该算法的平均复杂度及性能是比较优越的。
閤理安排鐵路專用線取送車順序,對提高調車機車作業效率、加速貨車週轉具有重要的意義。在已知條件下,以機車在裝卸點間走行時間為權,把樹枝形專用線取(送)車作業優化問題轉換成哈密爾頓圖最短路問題,併鬆弛為指派問題,採用匈牙利算法求齣指派問題的最優解,可得到最短迴路路長的下界或最優解。若未得到最優解,再利用破圈連接法求齣滿意的取(送)車順序,此算法的複雜度為O(n2)。同時對送兼調移、取兼調移、取送結閤、送調取結閤作業形式進行瞭深入地討論。最後舉例說明瞭模型的構造及求解過程。大量小規模案例錶明,該算法的平均複雜度及性能是比較優越的。
합리안배철로전용선취송차순서,대제고조차궤차작업효솔、가속화차주전구유중요적의의。재이지조건하,이궤차재장사점간주행시간위권,파수지형전용선취(송)차작업우화문제전환성합밀이돈도최단로문제,병송이위지파문제,채용흉아리산법구출지파문제적최우해,가득도최단회로로장적하계혹최우해。약미득도최우해,재이용파권련접법구출만의적취(송)차순서,차산법적복잡도위O(n2)。동시대송겸조이、취겸조이、취송결합、송조취결합작업형식진행료심입지토론。최후거례설명료모형적구조급구해과정。대량소규모안례표명,해산법적평균복잡도급성능시비교우월적。
Reasonable scheduling for placing-in and taking-out wagons in railway siding is of great significance to improve the operation efficiency of shunting locomotive and speeding up wagon’s turn-round. Under given conditions, taking the locomotive running time between sites as weights, the paper transforms the problem of placing-in (or taking-out) wagons into the shortest route problem of Hamilton graph and changed as assignment problem. The Hungarian algorithm is applied to calculate the optimal solution of the assignment problem. Then the lower bound or optimal solution of shortest route is obtained. If it is not a optimal solution, the broken-circle and connection method designed will be applied to find the satisfactory order of placing-in and taking-out wagons, and its computation complexity is O(n2). The paper simultaneously makes a deep discussion on other forms, such as placing-in and transferring combined, taking-out and transferring combined, placing-in and taking-out combined, placing-in-transferring and taking-out combined. Finally, an example is given to illustrate the model’s formulation and solution process. A large number of small cases also show that the algorithm’s average complexity and performance is relative superior.