规划问题算法-邮路规划与邮车调度最优化理论研究.pdf资源-CSDN文库

版权申诉

11 浏览量 2022-05-01 20:00:06 上传评论收藏 803KB PDF 举报

资源推荐

资源详情

资源评论

全

国

第

四

届

研

究

生

数

学

建

模

竞

赛

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

摘要：

本文对小规模 NP 类邮路规划与邮车调度问题,建立了可精确求解方案的 0-1

规划模型,并在满足邮政运输需求的前提下给出了最佳方案。问题一首先以县支

局、县局为顶点构建无向赋权图,建立最短路模型,求解各局间的最短距离阵 D，

其中顶点到自己路程为 0；然后在 D 的基础上以

ijk

(第 i 条邮路第 j 次是否收发

第 k 支局邮件)为决策变量,以邮车工作时间、车辆运载能力为主要约束，建立以

总空载损失费用最小为目标的 0-1 非线性规划模型,运用规划软件 Lingo 得到最优

或次优解 59.8154 元，具体邮路规划与邮车调度见 5.2.3。问题二考虑到市邮路成

本，我们采用分层规划策略，首先以市支局、县局为顶点构建无向赋权图,求解

出最短路矩阵 D20,以

ijk

为决策变量,邮车工作时间为主要约束,建立以邮路运行

成本最小为目标的 0-1 非线性规划模型,求解得到最优或次优解 2×2742 元，邮路

规划与邮车调度见 6.1.3；然后,建立各县区的最短路矩阵 D21～D25，同样建立

规划模型Ⅱ(ii)可求解得到最优或次优解,其中时间约束较复杂见 6.2.1；最后,全市

总运行费用为 9549 元,全市邮路规划与邮车调度见 6.2.3。问题三由于县局地理位

置不变,对区邮路无影响,故我们以全市各县支局为中心采用逐步最优方法对所有

县区支局重新划分，得到的县分区方案见 7.2；然后构建所有新县区无向赋权图,

得到最短路矩阵 D31～D35，采用第 2 问规划模型Ⅱ(ii),得到全市总运行费用为

9267 元,邮路规划与邮车调度见 7.3.3，结论是降低成本并不非常明显。所以在第

四问中考虑县局迁移，建立了全局选址规划模型,但模型规模较大,我们建立近似

的启发式算法完成县局选址(见 8.3),随后以 D21～D2 为最短路矩阵,运用模型Ⅱ(ii)

求解得到目标值 8997 元,邮路规划与邮车调度见 8.3 表 4.2;在此基础上我们还考

虑县局拉送邻县较近站点,同样使用模型Ⅱ(ii)对新县区划分的邮路规划求解,得

到目标值 8865 元,具体方案见表 4.4；最后还对邮路规划进一步松弛推广与研究。

关键字：无向赋权图 0-1 非线性规划

参赛队号 1042609 参赛学校青岛科技大学

参赛队员姓名汤志高王继利曹莹瑛

参赛密码

（由组委会填写）

题号 D

1 问题重述

邮政运输网络采用邮区中心局体制，即以邮区中心局作为基本封发单元和网

路组织的基本节点，在此基础上组织分层次的邮政网。邮路是邮政运输网络的基

本组成单元，本题即为对目标区域的邮路规划与邮车调度问题。

下面为本文所要研究的地区的邮政运输流程及时限规定：

Step1:区级第一班次邮车从地市局D出发将邮件运送到各县局Xi和沿途支

局，并将各县局Xi和沿途支局收寄的邮件运送回地市局D；区级第一班次邮车出

发时间必须在06:00之后，返回地市局D时间必须在11:00之前。

Step2:县局Xi将当天区级第一班次邮车及前一天的区级第二班次邮车所送

达的本县邮件进行集中处理，按寄达支局装上相应的县级邮车；县局Xi对邮件的

集中处理时间为1小时（包括邮件的卸装、分拣封发等处理时间）。

Step3:各县级邮车将邮件运送到其负责的支局并将这些支局收寄的邮件运

送回县局Xi；

Step4: 区级第二班次邮车从地市局D出发将邮件运送到各县局Xi和沿途支

局，并将各县局Xi收寄的邮件（包括当日各县级邮车运回县局Xi的邮件）和沿途

支局收寄的邮件运送回地市局D；请注意区级第二班次邮车在县局Xi卸装完邮件

后的出发时间必须在县局Xi的全部县级邮车返回县局并集中处理1小时以后，最

终返回地市局D的时间必须在18:00之前。

在上述规定下，假设区级两个班次邮车的行驶路线相同，要求区级邮政运输

网必须至少覆盖该地市附近的16个支局Z58, Z59, ……, Z73和5个县局X1，……，

X5。各县级邮政运输网必须覆盖本县内区级邮车不到达的支局。该地区邮局间公

路网分布见表1，并且县级邮车平均时速为30km/h，区级邮车的平均时速为

65km/h，邮车在各支局卸装邮件耗时5分钟，在各县局卸装邮件耗时10分钟。

问题1：以县局X1及其所辖的16个支局为研究对象，假设区级第一班次邮车

08:00到达县局X1，区级第二班次邮车16:00从县局X1再出发返回地市局D，若每

辆县级邮车最多容纳65袋邮件，试问最少需要多少辆邮车才能满足该县的邮件运

输需求？同时，为提高邮政运输效益，应如何规划邮路和如何安排邮车的运行？

（空车率=(邮车最大承运的邮件量(袋)-邮车运载的邮件量(袋))/邮车最大承运

的邮件量(袋)，单车由于空车率而减少的收入为（空车率*2元/公里））

问题2：采用尽可能少、尽可能短的邮路可以减少邮政部门车辆和人员等的

投入，从而降低全区邮政运输网的总运行成本。考虑投入较好的邮车，每条邮路

只需要一辆邮车即能满足运载能力要求，试问应如何构建该地区的邮政运输网络

（县的划分不变更），请给出邮路规划和邮车调度方案。邮车的调度必须满足上

文中有关该地区的邮政运输流程及时限规定。（每条邮路的运行成本为3元/公里）

问题3：考虑到部分县与县交界地带的支局，其邮件由邻县县局负责运送可

能会降低全区的运行成本，带来可观的经济效益。若允许在一定程度上打破行政

区域的限制，你能否给出更好的邮路规划和邮车调度方案？（在此同样不必考虑

邮车的运载能力的限制，每条邮路的运行成本为3元/公里）

问题4：县局选址的合理与否对构建经济、快速的邮政运输网络起到决定性

的作用。假设图2中县局X1，……，X5均允许迁址到本县内任一支局处，同时原

来的县局弱化为普通支局。设想你是该地区网运部门负责人，请你重新为各个县

局选址，陈述你的迁址理由并以书面材料形式提交省局网运处。

2 问题分析

本题为邮政运输网络中的邮路规划和邮车调度问题，在构建邮运网络时，首

要考虑的问题应是怎样在满足该市邮政运输流程及时限要求的前提下，用尽可能

少的邮路覆盖该市内所有邮局，同时，需在在运输成本尽量低的目标下对邮路进

行具体规划及对邮车进行合理调度。

规划的终极目的为使邮政运输效益最大。则首先应使所用邮车数量尽量少，

在此基础上，对第一问而言应使由空载率而损失的费用尽量小，其余各问皆为使

邮路运行成本尽量低。在网络构建时主要考虑以下几方面约束因素：

(1) 邮车运输时限约束：所有邮车需在运输流程中指定的时间内完成运输任务；

(2) 运输任务约束：邮车须将寄达、寄出各支局的邮件全部运送完；

(3) 邮车运输能力限制：邮车上所载邮件数目不能超过上限(65 袋)；

(4) 区及县网的构建必须覆盖其行政区域内的所有邮局。

在允许一定程度上打破现有县的划分时，应首先根据就近原则对各县网中支

局重新进行归属划分，然后在新支局归属划分下重新对县级邮路网络进行规划并

给出具体邮车调度方案。

在第四问中涉及到了县局选址问题，在假设当前县局均允许迁址到本县内任

一支局处，同时原来的县局弱化为普通支局，此时应综合考虑区级与县级两级网

络，对全市邮运网络进行全局整体构建。

3 模型假设

[1] 假设一辆邮车仅负责一条邮路；

[2] 假设一个邮局的邮件仅由一辆邮车运送；

[3] 假设区、级邮车行驶中皆以其平均时速 65、30km/h 运行；

[4] 假设区级两个班次邮车的行驶路线相同，但方向可以不相同；

[5] 对于区车覆盖的各县中的支局，两班车允许仅有一班进行邮件装卸。

4 符号说明

—— 图中节点

到

的最短路距离（由最短路模型求得）

ijk

—— 0-1 变量，表示第

辆车第

次装卸邮件是否在第

个节点

—— 表示县级车运输的最大时间范围（

的确定详见 6.2.1/(1)）

—— 第

个支局寄出的邮件总量

—— 寄达第

个支局的邮件总量

5 X1 所在县邮路规划及邮车调度模型（问题一）

本问以县局 X1 及其所辖的 16 个支局 Z1, Z2, ……, Z16 为研究对象，研究

满足该县的邮件运输需求的最少邮车数量，同时，在运输效益最大的目标下，对

邮路进行规划并对邮车进行具体安排。

5.0 模型准备

1）问题一模型假设

[1] 假设一辆邮车仅负责一条邮路；

更多数学建模资料请关注微店店铺“数学建模学习交流”

https://k.weidian.com/RHO6PSpA

[2] 县车一次即将支局的邮件全部装卸完；

[3] 假设一个站点的邮件仅由一辆邮车运送；

[4] 县级邮车行驶中皆以平均时速 30km/h 运行；

[5] 假设该县级邮政运输网必须覆盖本县内所有支局。

2）邮路网络的图论模型抽象

引用图论相关知识，将题中所提供的邮路网络抽象成一个连通网络图

( , , )G V E W





中的每个顶点为各级邮政局, 如果从



中的顶点

到

有直达

路线，那么这两点之间就用有边相连, 记做

( , )

i j E

，相应的有一个数

( , )

i j

w v v

称

为该边的权，其权值赋为两顶点间最短距离。

本问所建立的邮路网络中有多个圈，其中每个圈为一条邮路，各圈务必在

处相交。建图时将本县内

1, 2,..., 16Z Z Z

各支局编号为 1



16，

编号为 17，即

本县邮运网络图中共有 17 个顶点，在此抽象基础上进行分析建模。

5.1 邮局间最短路矩阵的建立

由于题中表 1 仅提供了可直达的两支局间距离，而在邮路规划时，当两支局

间无直达线路时需要路过其它支局才能到达。由此，需首先计算任两节点间的最

短路径，并进一步求出任两支局间最短距离。在邮路规划及邮车运行安排时任两

节点间的路径选择应为最短路。

根据表 1 中提供的图中任两节点间可直达的线路，可得该图的邻接矩阵

18 18

( )

A a





，以

表示可直达的两点

与

之间的距离，现需求从顶点

→

的

最短路径。设 0-1 决策变量为

，当

x 

1 时，说明弧

( , )i j

位于顶点

至顶点

的路上；否则，

x 

0，则可得求任两顶点

→

最短路的模型如下：

Min

( , )

ij ij

i j E

w x





   

1 1

, ,

1 ( )

. .

0 ( , )

0 , ( , )

n n

ij ji

j j

i j E i j E

i s

x x i e

s t

i s e

x i j E

 

 

 





   















 



 

根据此模型可求解出由

所在县构成的图中任两顶点间的最短路线矩阵，

矩阵中各元素表示任两节点间的最短路线，并可根据路线中各弧的长度及邮车平

均时速 30km/h 求得邮车在任两节点间运输的最短距离矩阵

18 18

( )



,见附录 1.1。

5.2

所在县邮路规划及邮车调度模型

5.2.1 模型Ⅰ分析

本模型建立首先要求确定最少邮车数目，并在邮车数最少的基础上，以运输

效益最大为目标（使由于空车率而减少的收入尽量少），对该县邮路进行规划并

给出邮车调度方案。

在求解时，需要满足以下邮运约束：



邮车运输时限约束：所有邮车需在指定时间内完成运输任务；



运输任务约束：邮车须将寄达、寄出各支局的邮件全部运送完；



邮车运输能力限制：邮车上所载邮件数目不能超过上限(65 袋)；



该县级邮政运输网必须覆盖本县内所有支局；



各邮车每次仅到一个支局装卸；



本县邮车始、终点为

。

下面分别对以上约束及目标进行分析，并建立最优化模型求解。

约束分析

(1) 邮车运输时限约束

由题中关于该区邮政运输流程的规定，可知各县级邮车必须在第一班区级邮

车到来后，并对邮件进行集中处理一小时后才能出发，且必须在第二班区级邮车

出发前一小时到来（提前一小时到是为了对邮件进行集中处理一小时）。

根据问题一假设，区级第一班次邮车 08:00 到达县局 X1，区级第二班次邮

车 16:00 从县局 X1 再出发返回地市局 D；除去前后共 2 小时的邮件处理时间，

该县的邮车一天最多可运送 6 小时。

引入 0-1 变量

ijk

表示第

辆车第

次装卸邮件是否在第

个支局，即：

ijk

i j k









第辆车第次装卸邮件在第个支

局

否则

设第

辆车最多经过

个节点，则第

辆车共在

1 1

ijk

j k

 



个支局进行了装卸

邮件工作，题中给出邮车在各支局装卸邮件耗时 5 分钟，则第

辆车在运输过程

中耗费在各支局装卸邮件的时间为：

1 1

ijk

j k

T F

 





(h)

结合

ijk

定义可知，当且仅当

ijk

与

i j q

，

，

同时为 1 时表示第

辆车由支局

到支局

，即经过弧

( , )k q

，其余情况为不经过。则可用

, 1,ijk i j q

F F





来表示第

辆

是否经过弧

( , )k q

，即：

, 1,

1 ( , )

0 ( , )

ijk i j q

i k q

F F

i k q





 





第辆车经过弧

第辆车不经过弧

已知各县级车平均行驶速度为 30km/h，以

表示第

个支局到第

个支局

的最短路距离（由 5.1 求得的最短路矩阵确定），即

为弧

( , )k q

的长度，则第

辆车运输途中耗时为：

1 17 17

2 , 1,

1 1 1

ijk i j q

j k q

T F F





  





(h)

邮车在运输过程中耗时由在各支局装卸邮件耗时及运输途中耗时两部分构

剩余39页未读，继续阅读

评论收藏

内容反馈

版权申诉

普通网友

粉丝: 12w+
资源:
9336

规划问题算法-邮路规划与邮车调度最优化理论研究.pdf

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

规划问题算法-邮路规划与邮车调度.pdf

邮政运输网络中的邮路规划和邮车调度优化研究.doc

规划问题算法-邮政运输网络中的邮路规划和邮车调整.pdf

规划问题算法-邮政运输网络中的邮路规划和邮车调度.pdf

图论loyd算法算法-邮政运输网络中的邮路规划和邮车调度.pdf

粒子群算法-邮政运输网络中的邮路规划和邮车调度.pdf

规划问题算法-邮政运输网络中的邮路规划和邮车调整 (2).pdf

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

邮政运输网络中的邮路规划和邮车调度MATLAB源代码

图论Dijkstra模型-邮政运输网络中的邮路规划和邮车调度.pdf

【路径规划】基于FLOYD算法实现邮政运输网络中的邮路规划和邮车调度matlab代码.zip

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

【VRP】基于matlab求解邮路规划和邮车调度问题【含Matlab源码 648期】.zip

大数据-算法-时变中国邮路问题的整数规划模型及算法研究.pdf

数学建模-2007年D题 邮政运输网络中的邮路规划和邮车调度（终）.zip

数学建模-邮政运输网络中的邮路规划和邮车调度.zip

调度方法.zip_brassmqn_调度_运输_邮路规划_邮车调度

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

求解最优化问题的类电磁机制算法研究.pdf

论文研究-最优化问题全局寻优的AFSA-BFGS混合算法.pdf

大数据-算法-最优化问题算法模式的研究.pdf

大数据-算法-窗时排序问题中的最优化算法研究.pdf

大数据-算法-最优化理论求解钻柱接触非线性问题.pdf

数学建模-1042202邮政运输网络中的邮路规划和邮车调度.zip

音视频-编解码-最优化问题的梯度投影算法研究.pdf

相关实用应用程序（Windows可用）

免费可用的ChatGPT网页版.zip

最新资源

数学建模-2007年D题邮政运输网络中的邮路规划和邮车调度（终）.zip