邮政运输网络中的邮路规划和邮车调度1.doc

邮政运输网络中的邮路规划和邮车调度
【摘要】:本题主要以现实中邮政网络规划问题为研究对象,在研究过程中针对不同情况下的最佳邮路设计和运输效益问题,分别建立了线性规划模型,并利用matlab软件搜索求解。
针对问题一,首先利用matlab元胞数组功能录入x1县的邮政信息,建立包含各支局收、寄邮件数量和各线路行驶时间的数据库,然后在同时满足各线路邮件运输量不超过邮车最大承载量和各线路邮车运输时间不超过规定时限的条件下,调用数据库中相关信息并利用matlab软件搜索所有符合条件的邮路,其次以使用最少邮路覆盖全县邮政网络为目标,建立关于邮路设计的线性规划模型,并利用matlab软件求解得,覆盖全县最少需规划3条邮路即最少使用3辆邮车就可满足全县邮件运输需求,最后在满足上述求解结果的条件下结合空车率计算方法,以减少收入最低为目标建立关于邮车调度的线性规划模型,利用matlab软件搜索求解得3辆邮车的具体路线安排分别为:x1-12-13-1-3-2-5,x1-4-6-9-11-10,x1-14-15-16-8-7,此时因空车率而降低的总收入为:。
针对问题二,通过对题目的分析,首先利用贪婪算法寻找市局内可到达各县局的最近支局,并将其作为通往各县局邮路在市区内的终点和在各县局内的起点,其次在确定市区和各县局内邮路的起点和终点后,在同时满足从市局出发的各邮路可完全覆盖市局邮政网络和各邮路运行时间不超过规定时限的条件下,以邮路总运行费用最少为目标,建立线性规划模型,并利用贪婪算法逐步寻找最优解,最后解得市局需5辆邮车,各县局分别需要:2,2,0,0,2辆邮车,,,具体安排见模型求解。
关键词: 线性规化搜索求解贪婪算法
1、问题重述
问题的来源及意义:
在信息技术飞速发展的今天,互联网已经成为一种重要的通信手段,但在我们利用Email等方式交流信息的同时,邮政作为传统的通信手段仍然与我们的日常生活和工作息息相关,发挥着不可替代的作用。时限与成本是邮政运输问题的两个重要指标。时限是指邮电部规定的邮件、报刊处理、传递的最大时间限制,时限关系到邮政通信质量的好坏;成本影响着企业的经营。
邮政运输网络是邮政企业运营的重要保障,是决定邮政企业竞争能力的主要因素。
提出问题
[1]以县局X1及其所辖的16个支局Z1, Z2, ……, Z16为研究对象,假设区级第一班次邮车08:00到达县局X1,区级第二班次邮车16:00从县局X1再出发返回地市局D,若每辆县级邮车最多容纳65袋邮件,试问最少需要多少辆邮车才能满足该县的邮件运输需求?同时,为提高邮政运输效益,应如何规划邮路和如何安排邮车的运行?
[2]采用尽可能少、尽可能短的邮路可以减少邮政部门车辆和人员等的投入,从而显著降低全区邮政运输网的总运行成本。考虑投入车况较好的邮车,通常每条邮路只需要一辆邮车即能满足运载能力要求,试问应如何构建该地区的邮政运输网络(县的划分不能变更),请你给出邮路规划和邮车调度方案。请注意邮车的调度必须满足上文中有关该地区的邮政运输流程及时限规定。
2、问题分析
本题主要以现实生活中的邮路规划和邮车调度问题为研究对象,在研究过程中需考虑各支局之间是否可到达,邮车的调度是否满足题目要求和安排的邮路是否能覆盖邮政网络等因素。解决邮路规划和调度问题时需要明确以下几个方面:
①邮路的形式与种类
在邮政运输网络中,将各地市局、县局、支局都近似看做结点,任意两点的连线都可看做是一条路径,邮路类型主要有环形、辐射型和混合型三种,由于实际邮政运输网络中存在两个邮局间无可到达路线的情况且并非所有支局都可直达县局,因此,根据邮局间直达的情况即可推算出各条邮路的线路类型。
②线路搜索方法
本文的关键是搜索方法的科学性,应首先寻找出所有的线路,其次,搜索同时满足每辆车的时限要求和邮车最大运载量的线路,即记录所有同时满足时限要求和最大运输量的线路,最后,根据线路是否覆盖所有支局且无重复数据得到最终的可到达线路。
③不同要求下对时限的理解与计算
时限指的是邮电部规定的额邮件、报刊处理和传递的最大时间限制。在调度邮车的过程中主要考虑邮车在行驶过程中的耗时、在支局或县局的卸装时间、处理邮件的时间。对不同区域或规定时限其计算方法是不同的。
3、模型假设
[1] 假设邮车在行驶过程中不会存在意外的等待时间;
[2] 假设区级第一班次的邮车到达区级后的处理时间不予考虑;
[3] 假设车况较好的邮车没有最大运载量的约束;
[4] 假设不同邮车在不同时间到达支局或县局的卸装、分拣封发和等待时间等都是相同的;
[5] 假设不同县局邮车经过的支局各不相同,即一个支局只能由一辆邮车