资源描述：
《邮路规划与邮车调度最优化1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第38卷第14期数学的实践与认识Vol138No1142008年7月MATHEMATICSINPRACTICEANDTHEORYJuly,2008邮路规划与邮车调度最优化理论研究122汤志高,王继利,曹颖瑛21指导教师:曹华林,梁希泉(1.青岛科技大学数理学院,青岛266061)(2.海军航空工程学院(青岛)航空机械系,青岛266041)摘要:对小规模MTSP问题,建立了可精确求解方案的0-1规划模型,并在满足邮政运输需求的前提下给出了最佳方案.问题一首先以县支局、县局为顶点构建无向赋权图,通过Floyd算法求解各局间的最短距离;然后以Fijk为决策变量,以邮车工作时间、车辆运载能力为主
2、要约束,建立以总空载损失费用最小为目标的021非线性规划模型É,运用规划软件Lingo求解.问题二考虑到市邮路成本,我们采用分层规划策略,首先以市支局、县局为顶点构建无向赋权图,求解出最短路矩阵,建立以邮路运行成本最小为目标的0-1非线性规划模型IIA求解;然后,建立各县区的最短路矩阵,同样建立规划模型IIB求解各县运输方案.问题三由于县局地理位置不变,对区邮路无影响,故以全市各县支局为中心采用逐步最优方法对所有县区支局重新划分;然后采用模型IIB求解.第四问中考虑县局迁移,我们建立近似的启发式算法完成县局选址,并运用规划模型II求解的到新方案.最后,我们对两种区域划分调整方法还进行了定
3、量的分析.关键词:无向赋权图;021非线性规划1模型假设1)一辆邮车仅负责一条邮路;2)一个邮局的邮件仅由一辆邮车运送;3)区、县级邮车行驶中皆以其平均时速65、30kmöh运行;4)区级两个班次邮车的行驶路线相同,但方向可以不相同.2符号说明dkq——图中节点k到j的最短路距离;Fijk——表示第i辆车第j次装卸邮件是否在第k个节点;QGk——第k个支局寄出的邮件总量;HGk——寄达第k个支局的邮件总量.3模型É3.1邮局间最短路径由于题中仅提供了两支局间直达距离,但这不一定是最短距离.因此,首先需要利用Floyd算法把各支局间的最短路径矩阵D求出.3.2模型分析邮车运输时限约束收稿日
4、期:2008204201202数学的实践与认识38卷m16设第i辆车最多经过m个节点,则第i辆车共在∑∑Fijk个支局进行了装卸邮件工作,j=1k=1题中给出邮车在各支局装卸邮件耗时5分钟,则第i辆车在运输过程中耗费在各支局装卸邮件的时间为:m165T1=60∑∑Fijk(h)j=1k=1结合Fijk定义可知,当且仅当Fijk与Fi,j+1,q同时为1时表示第i辆车由支局k到支局q,其余情况为不经过.1第i辆车经过弧(k,q)FijkõFi,j+1,q=0第i辆车不经过弧(k,q)已知各县级车平均行驶速度为30kmöh,以dkq表示第k个支局到第j个支局的最短路距离,则第i辆车运输途中耗
5、时为:m-11717dkqT2=∑∑∑30FijkFi,j+1,q(h)j=1k=1q=1第i辆车邮运过程总耗时不超过运输时限(6小时)约束可表示为:m16m-117175dkqT1+T2=60∑∑Fijk+∑∑∑30FijkFi,j+1,qF6(i=1,⋯,n)(1.1)j=1k=1j=1k=1q=1邮车运载能力限制根据问题一要求,每辆县级邮车最多容纳65袋邮件,这里实际上限制了两个方面:其一,每辆车在出发时装载所要运送的所有邮件量,而这些邮件需要在沿途支局全部卸下,所以各车卸下的邮件总量不能超过65袋;其二,邮车在经过支局时卸下一部分邮件,同时收取一部分邮件,则在每个分局装卸完成后,
6、各车上所载邮件数不超过65袋.H以Gk表示寄达第k个支局的邮件总量,第i辆车最多经过节点数为m,Fijk表示第i辆车第j次装卸邮件是否在第k个支局,则第i辆车在出发时装载的所要运送的所有邮件量为:m16H∑∑FijkGkj=1k=1Q邮车在运输途中不断装卸邮件,以Gk表示第k个支局寄出的邮件总量,则经过第k个支QH局时邮车上邮件数量变化量为Gk-Gk,第i辆车在出发时及运输途中邮件总量始终不超过邮车运载能力(65袋)约束可表示为:m16q16HQH∑∑FijkGk+∑∑Fijk(Gk-Gk)F65(q=1,2,⋯,m)(1.2)j=1k=1j=1k=1覆盖本县内所有支局设最少需要n量邮车
7、,第i辆车最多经过节点数为m,Fijk表示第i辆车第j次装卸邮件是否在第k个支局,则该县级邮政运输网必须覆盖本县内所有支局且仅覆盖一次可表示为:nm∑∑Fijk=1(k=1,2,⋯,16)(1.3)i=1j=1各邮车每次仅到一个支局装卸由于Fijk表示第i辆车第j次装卸邮件是否在第k个支局,则只要经过第k个顶点则Fijk=1(注意,此处经过某一邮局不一定有邮件的装卸工作,可能仅仅是路过,则装卸量为零).14期汤志高,等:邮路规划与邮
