邮路规划与邮车调度最优化理论研究  

Optimization Theory Research on Post Route and Mail Cart

作　　者：汤志高[1] 王继利[2] 曹颖瑛[2] 曹华林[2] 梁希泉[1] 

机构地区：[1]青岛科技大学数理学院,青岛266061 [2]海军航空工程学院(青岛)航空机械系,青岛266041

出　　处：《数学的实践与认识》2008年第14期201-209,共9页Mathematics in Practice and Theory

摘　　要：对小规模MTSP问题,建立了可精确求解方案的0-1规划模型,并在满足邮政运输需求的前提下给出了最佳方案.问题一首先以县支局、县局为顶点构建无向赋权图,通过Floyd算法求解各局间的最短距离;然后以Fijk为决策变量,以邮车工作时间、车辆运载能力为主要约束,建立以总空载损失费用最小为目标的0-1非线性规划模型,运用规划软件Lingo求解.问题二考虑到市邮路成本,我们采用分层规划策略,首先以市支局、县局为顶点构建无向赋权图,求解出最短路矩阵,建立以邮路运行成本最小为目标的0-1非线性规划模型IIA求解;然后,建立各县区的最短路矩阵,同样建立规划模型IIB求解各县运输方案.问题三由于县局地理位置不变,对区邮路无影响,故以全市各县支局为中心采用逐步最优方法对所有县区支局重新划分;然后采用模型IIB求解.第四问中考虑县局迁移,我们建立近似的启发式算法完成县局选址,并运用规划模型II求解的到新方案.最后,我们对两种区域划分调整方法还进行了定量的分析.As to the in miniature MTSP problem, O--1 programming models are developed that can give precise Solutions in this paper, and best solutions are obtained on the premise that the requirements of post transportation are satisfied. In the first problem, an undirected weighted diagram is established with the county branch post offices and county post offices as vertexes, and the shortest distance between each two post offices can be calculated by Floyd algorithm. Then make Fijk be the decisive variable and let the working time and carrying capacity of vehicle be the main constraints to develop the 0-1 nonlinear programming model I with the total fare lost of no-load as the objective. Programming software Lingo is used to solve this model. In the second problem, layered programming strategy is adopted considering the city post transportation cost. At first, we establish an undirected weighted diagram with the branch city post offices and county post offices as vertexes, obtain the shortest path matrix, and develop the 0-1 nonlinear programming model II A with minimum post transportation cost as the objective. Then we establish the shortest path matrix of county post offices and develop programming model lib similarly to get transport solutions of each county. In the third problem ,because the geographical location of each county post office doesn＇t change and it has no influence to county post route, we redivide all the county branch post offices by optimal method step by step centering on each branch post office in the whole city; then develop model lib to solve it. In the fourth problem, we develop approximate heuristic algorithm to select address for county post offices and develop programming models II to get new solutions. At the end, we make quantitative analysis about the two region division adjusting methods.

关 键 词：邮路规划 邮车调度 无向赋权图 0-1非线性规划 

分 类 号：F618[经济管理—产业经济] U492.3[交通运输工程—交通运输规划与管理]