A题--物流调度优化(共19页)

《A题--物流调度优化(共19页)》由会员分享，可在线阅读，更多相关《A题--物流调度优化(共19页)（19页珍藏版）》请在装配图网上搜索。

1、精选优质文档-倾情为你奉上A题 物流调度优化物流调度是城市发展过程中亟待解决的现实问题。在如下图所示的城市中有N=31个物资仓库，任意两个仓库的运出物资互不相同，仓库的位置坐标见附表1。我们约定序号为i ( i取值0, , N-2 )的仓库与序号为i+1的仓库之间有道路直接相连，同时，任何两个仓库之间，只要他们之间的直线距离介于10到15之间，也都有道路直接相连。现在有一些物资需要在仓库之间周转，周转任务见附表2。假设每个仓库的卡车数目与每台卡车的载重没有上限，但是每一条道路的任一侧都有同时在运的重量上限Wmax=50。汽车以每小时10个单位长度的速度在道路上行驶，可以在途中的任何一个仓库休息

2、以等待可用的道路。试问：（1） 若全部完成运输任务1（不用返回），最少需要多少时间？（2） 假设同一仓库的运输任务1和任务2所运物资相同，那么同时完成各自的两个任务（都不用返回）最少需要多少时间？题目 物流调度问题 摘要本文是对城市发展中车流调度问题的研究，通过对题目所给条件的分析，紧抓总运输时间最小这一目标，构建数学模型，求出完成任务的最短时间。问题一要求依据附表1和附表2，在不考虑返回的情况下，计算出完成任务1所需的最短时间。统计附表1中的仓库坐标信息作为原始数据，将该问题看作一个最优可行流问题。分析各仓库之间的具体道路连接情况，将其中的运输路程单位定义为一个单位长度，列出约束条件，用约束

3、条件和仓库与仓库之间的距离关系对问题进行数学上的描述，建立如下目标规划模型：利用蒙特卡洛算法，通过随机抽取既定道路的方法对该问题进行求解，多次试验后发现结果趋于一个稳定值即为满意解，得到完成任务1所需的最短时间单位时长。问题二要求依据附表1和附表2，在不考虑返回的情况下，当同一仓库的运输任务1和任务2所运物资相同时，同时完成各自的两个任务所需的最短时间。通过类比问题一的只完成任务1的情况，运用转化思维，将该问题倒置考虑，即计算从两个不同仓库将货物运送到一个仓库中所需的最短时间，建立如下模型：采取与问题一相同的算法，通过目标规划以及蒙特卡洛算法，求得同时完成各自任务所需的最短时间单位时长。关键词

4、 最优可行流 目标规划 蒙特卡洛算法 转化思维 一、问题重述1.1背景分析近年来，随着现代社会经济的高速发展以及各种信息物资的频繁交流，我国的物流业迅速发展，尤其是电子商务的快速发展及区域间经济互动的不断加强，为物流配送提供了巨大的发展契机。但在同时也造成了一个问题，即由于物流网络规模的壮大，物流量的巨大增加，以往的手工作业或简单的计算机作业处理方式已经不能满足迅速发展的业务要求。由于配送是物流系统的重要环节，该环节的运行效率将直接影响对客户需求的响应时间及服务成本。因此，如何经济合理组织送货，如何保证配送系统高效及低成本的运作成为普遍研究的热点。1.2问题重述有一些物资仓库，其数量为31（仓

5、库的位置坐标具体见附表1），其中任意两个仓库的运出物资互不相同。我们约定序号为的仓库与序号为的仓库之间有道路直接相连（的取值为0,1，）,同时，任何两个仓库之间，只要他们的直线距离介于10到15之间，也有道路直接相连。现有一些物资需要在仓库之间周转，周转任务见附表2。假设每个仓库的卡车数目与每台卡车的载重没有上限，但是每一条道路的任一侧都有同时在运的重量上限。汽车以每小时10单位长度的速度在道路上行驶，可以在途中的任何一个仓库休息以等待可以的道路。根据提供的附表1和附表2，参考相关文献，解决以下问题：1、若全部完成运输任务1（不用返回），最少需要多少时间？2、假设同一仓库的运输任务1和任务2所

6、运物资相同，那么同时完成各自的两个任务（都不用返回）最少需要多少时间？二、问题分析2.1对于问题一的分析本小问要求依据所提供的附表1与附表2（具体见附录），在不考虑返回的情况，求出完成运输任务1所需的最短时间。所谓最短时间，即是对于该问题需要求一个最优的策略，该策略可以使得达成所有运送目标的所花费的时间最短。通过观察附表1可发现，给出的坐标点多且乱，因此，可以先绘制出各仓库的位置点图以及各仓库间的连线情况图。进一步可发现要制定这个策略，可以采用目标规划这一方法，用约束条件和仓库与仓库之间的距离关系对问题进行数学上的描述，并在满足约束条件的情况下求得最优的运送方案。又由于要考虑的每一种的情况过于

7、复杂，所以可以采取蒙特卡洛算法，通过产生随机既定路径的方法对问题进行求解，如果多次试验产生的结果趋于一个稳定值，则认为得到了一个满意解，最终求出题目所要求的最短时间。2.2对于问题二的分析本小问要求在假设同一仓库的运输任务1和任务2所运物资相同的情况下，不考虑返回时间，求出同时完成各自的两个任务所需的最短时间。显然，对于问题二，需要将任务1和任务2都完成，并且所花费的时间最短。问题一已经研究过只完成任务1所需的最短时间，所以在问题二中可以将问题倒置考虑。原题是将同一商品从一个仓库运往不同的两个仓库，可以转化为将目标仓库作为起点，从两个不同的仓库将货物运送到同一个仓库中。可以采取与问题一相同的算

8、法，通过目标规划，用约束条件和仓库与仓库之间的距离关系对问题进行数学上的描述，以及由于该问题所要考虑的每一种情况过于复杂，故采取蒙塔卡罗的算法，最终求得问题所要求的最短时间。三、模型假设结合本题的实际，为了确保模型求解的准确性和合理性，我们排除了一些位置因素的干扰，提出以下几点假设：1、假设不考虑汽车在红绿灯、堵车、恶劣天气状况等情况下的延误时间；2、假设仓库与仓库之间的距离为整数；3、假设忽略运输车加速或制动的速度变化及时间的影响；4、假设在求解最短时间时不考虑实际情况中载重不同的运输车的固定成本的差异；5、假设本文引用的数据、资料真实可靠。四、符号说明为了便于问题的求解，我们给出以下符号说

9、明：（其他未说明的符号在文中第一次出现时会做详细的说明。）从仓库到仓库的运输时间（）从仓库到仓库的运进货物重量从仓库到仓库之间的路程第件商品的运输策略（）中转站的编号初始时间运输货物的重量新增时间第仓库到中转站的距离（）目标仓库编号五、模型的建立与求解经过以上的分析和准备，我们将逐步建立以下数学模型，进一步阐述模型的实际建立过程。5.1问题一模型的建立与求解问题一要求求出在不考虑车辆返回的情况下，全部完成运输任务1所需的最短时间。根据上述分析中引入的目标规划1这一方案，下面我们结合附表1 和附表2对其做出定性分析，给出求解过程。5.1.1实际仓库间道路连接情况的描述附表1显示的31个仓库具体的

10、位置坐标，先将仓库标号重新定义，即仓库（）由所给题目可知，任意两个相邻仓库之间有道路直接相连，同时，当两个仓库之间的直线距离介于10到15之间时，也有道路直接相连。因此，利用2对附表1中的数据进行处理，得到的各个仓库的坐标位置情况如下面图1所示：图1 各仓库位置坐标点图5.1.2目标规划模型的建立通过分析，对于问题一，可以将它看作为一个寻求时间最短的可行流问题3。我们的目标是让完成所有运送目标的时间尽可能的短，同时，又要满足另一个条件即在每一条道路的任一侧都有同时在运的重量上限：。此外，在满足这两个条件的同时，又要满足对于中转站而言，同一种类型的商品的运进货物重量和运出货物重量相同。对于运输，

11、我们假设存在这样一种策略,可以使得总体所花的时间最短，将第仓库的运输策略记为，从仓库到仓库的运输时间为，可以得到下列目标规划表达式：目标函数为：约束条件为：其中表示从仓库到仓库的运进货物重量，表示从仓库到仓库的运出货物重量，表示从仓库到仓库之间的路程。对于各仓库间的连线情况，我们通过的筛选处理，得到各仓库之间道路的具体连接情况，如下面图2所示：图2 各仓库间道路连接情况图为了找出可以使得运输时间达到最短的策略，我们可以采取蒙特卡洛算法对每一个货物的路径进行随机抽取。随机抽取的同时要满足以下条件：出货量等于收货量；每一条道路的任一侧同时运送的货物的数量不超过50，这样我们就不用考虑每一个商品在未

12、被运送到终点时的路线问题、等待问题和策略问题。具体的算法如下：1、对初始情况的描述分析附表1中的数据，对货物的初始状态进行描述。构造一个矩阵，该矩阵描述了货物的状态：矩阵分为五列，第一列代表了货物起始的仓库编号，第二列代表了中转站的编号，第三列代表了商品到达中转站的距离，第四列代表了货物的重量，第五列代表了目标仓库的编号，如下列式子所示：初始时，将中转站定为与起始仓库一样，则可以得到商品到中转站的距离为0。对于以上矩阵，如果该货物的重量大于50，就在矩阵后面再加上一行，该商品的重量减去50，并将50赋值给原来所对应的数据。对于矩阵，我们先将它赋值为初始状态，即第一列与第二列相同，每一点的距离为

13、0。2、对数据的搜索按照步长为一个单位对数据进行搜索，每走一个单位，将矩阵的第三列所对应的距离减少1，并进行如下判断：如果该数据出现了小于等于0的情况，就认为该货物已经达到了终点，此时用将中转站的编号替换初始状态的编号，并通过随机抽取与该点相连的路径的方式，同时把相连的点赋值给中转站所在的点，用两点间的路径代替原来的路径；如果该货物的中转站编号与终点的编号相同，并且路径的长度小于等于0，则代表该货物已经到达了终点。对于这种情况，我们将货物的运送量赋值为0。当所有货物的运送量都为0时，就代表了所有货物都已经运完，迭代4结束。在进行以上步骤的同时，给出一个计步器，每个商品每走一个单位长度，我们就让

14、计步器加1。而每一点的下一步情况通过自带的随机函数确定，当货物全部运送到终点时，计步器停止计数，得到的数值的大小就是本次所随机的策略所得到的长度，其时间即为长度数除以速度。其中，矩阵的状态可以表示为：其中（）代表了中转站的编号，（）代表了第个仓库到中转站的距离，代表了运输货物的重量，代表了目标仓库编号。通过上述方法，我们求得每一步的时间。将初始时间记为，每次找到一个时间就与初始时间进行比较。如果新的时间比初始时间小，我们就把数量较小的时间赋值给。这样经过多次的迭代计算，如果每一次所求出的最短时间收敛于同一个数值，那么我们就认为该问题的满意解为多次迭代所算出的时间中较小的那个。如果没有收敛于同一

15、数值，则进行多次实验，增加实验的次数，直到收敛于同一数值为止。5.1.3目标规划模型的求解由于随机选取满足正态分布，所以多次实验我们可以得到非常靠近最优解的满意解，这样就可以得出所要求的结果。结合上述各仓库间的道路连接情况图，利用求得各仓库之间道路距离，如下面表1所示：表1 各仓库之间道路距离道路序号123456道路长度514843434137道路序号789101112道路长度373634312929道路序号787980818283道路长度888766注：完整表格见附录其中，上述表格中道路长度的单位为一个单位长度。通过上述算法，最终求得最短时间单位时长。5.2问题二模型的建立与求解问题二要求求

16、出在不考虑返回以及同一仓库的运输任务1和任务2所运物资相同的情况下，同时完成各自的两个任务所需的最短时间。通过分析，发现问题二依旧是一个优化问题，对于该问题，我们依旧寻求一种最优策略使得完成这两个任务的最长时间最短。5.2.1实际任务完成思路的转换对于问题二，由于我们要将任务1和任务2都完成，并且所花费的时间最短，所以我们可以将问题倒置考虑。原题是将同一商品运往不同的两个仓库，现在我们可以考虑将目标仓库作为起点，从两个不同的目标仓库将货物运送到同一个仓库中。在运送的同时，依旧满足一下约束条件：条件1，每一条道路上同一方向上的运货量不能超过50；条件2，对于每一个中转站而言，进入的同种商品的重量

17、和等于输出的商品的重量和。通过以上分析，求得该题的最优策略。5.2.2问题二模型的建立与求解对于问题二,我们仍旧采取与第一问相似的处理方法，不过我们的目标是让完成所有运送货物的时间尽可能的短，同时，又要满足另一个条件即在每一条道路的任一侧都有同时在运的重量上限：。此外，在满足这两个条件的同时，又要满足对于中转站而言，同一种类型的商品的运进货物重量和运出货物重量相同。对于运输，我们假设存在这样一种策略,可以使得总体所花的时间最短，将第仓库的运输策略记为，从仓库到仓库的运输时间为，从仓库到仓库的运输时间为，可以得到下列目标规划表达式：目标函数为：约束条件为：其中表示从仓库到仓库的运进货物重量，表示

18、从仓库到仓库的运出货物重量，表示从仓库到仓库之间的路程。根据上一问通过对数据的筛选，得到各仓库之间道路的具体连接情况，为了找出可以使得运输时间达到最短的策略，我们可以采取蒙特卡洛算法对每一个货物的路径进行随机抽取。随机抽取的同时要满足以下条件：出货量等于收货量；每一条道路的任一侧同时运送的货物的数量不超过50，这样我们就可以忽略每一个商品在未被运送到终点时的路线问题、等待问题和策略问题。具体的算法如下：首先，分析附表1中的数据，对货物的初始状态进行描述。构造一个矩阵，该矩阵描述了货物的状态：矩阵分为五列，第一列代表了货物起始的仓库编号，第二列代表了中转站的编号，第三列代表了商品到达中转站的距离

19、，第四列代表了货物的重量，第五列代表了目标仓库的编号。初始时，将中转站定为与起始仓库一样，则可以得到商品到中转站的距离为0。其次，按照步长为一个单位对数据进行搜索，每走一个单位，将矩阵的第三列所对应的距离减少1，并进行如下判断：如果该数据出现了小于等于0的情况，就认为该货物已经达到了终点，此时用中转站的编号替换初始状态的编号，并通过随机抽取与该点相连的路径的方式，同时把相连的点赋值给中转站所在的点，用两点间的路径代替原来的路径；如果该货物的中转站编号与终点的编号相同，并且路径的长度小于等于0，则代表该货物已经到达了终点。对于这种情况，我们将货物的运送量赋值为0。当所有货物的运送量都为0时，就代

20、表了所有货物都已经运完，迭代4结束。在进行以上步骤的同时，给出一个计步器，每个商品每走一个单位长度，我们就让计步器加1。而每一点的下一步情况通过自带的随机函数确定，当货物全部运送到终点时，计步器停止计数，得到的数值的大小就是本次所随机的策略所得到的长度，其时间即为长度数除以速度。其中，矩阵的状态可以表示为：其中（）代表了中转站的编号，（）代表了第个仓库到中转站的距离，代表了运输货物的重量，代表了目标仓库编号。通过上述方法，我们求得每一步的时间。将初始时间记为，每次找到一个时间就与初始时间进行比较。如果新的时间比初始时间小，我们就把数量较小的时间赋值给。这样经过多次的迭代计算，如果每一次所求出的

21、最短时间收敛于同一个数值，那么我们就认为该问题的满意解为多次迭代所算出的时间中较小的那个。如果没有收敛于同一数值，则进行多次实验，增加实验的次数，直到收敛于同一数值为止。由于随机选取满足正态分布，所以多次实验我们可以得到非常靠近最优解的满意解，这样就可以得出所要求的结果。通过以上计算，最终求得最短时间单位时长。六、模型的检验由于对于路径的选择，我们将它设定为一个平均随机事件，所以我们得到的每一个时间应该是满足正态分布的，距离最优解百分之()的范围内的某一点，落在这一点的概率为0.0001，则该点不落在这个区间的可能性为0.9999，连续进行30000次实验，没有一个点落在这个区间的概率为 0.

22、0498，落在这个区间的概率大于95%，所以该方法存在可行性和合理性。时间的正太分布图如下面图3所示：图3 时间的正太分布图七、模型的评价与改进7.1模型的评价7.1.1模型的优点|1、规避了由于采取不同方法导致的复杂情况；2、解决了枚举每一种方法导致的计算量过大的问题；3、通过将步长调整为整数的方式再次降低了计算量；4、计算出来的结果是一个较为精确的满意解。7.1.2模型的缺点1、蒙特卡洛算法虽然大大简化了该题的运算过程，但其多次随机抽取行进路线的方式却存在遗漏最优解的风险，即只能求出满意解，无法判断最优解；2、整体统筹优化尽管规避了复杂繁琐的过程分析，但程序复杂，准确转化较为困难。7.2模

23、型的改进本题任意两点之间的距离为浮点型数据，而模型中我们假设蒙特卡洛计算一次，汽车前进一个单位长度（整型数据），存在误差。对汽车的单位步长进一步取短细化处理，可在最大程度上消除误差。本文中的程序创建前对路线图做更细致的处理，可提前筛选出一些特征较为明显的情形进行单独考虑，这样不仅能限制条件更加情形，还能简化程序，保证条件转化的准确性和高效性。但由于考虑到本文所用模型的可行性以及时间的问题，我们依旧采用文中所用方法。八、模型的推广本文运用了目标规划的相关知识，其运用数学定律，研究物资调度的问题。在本文中主要运用了目标规划的相关算法，通过相关约束条件的列举，求得满意解。由于现在人们对经济利益的追求

24、更加强烈，希望各种资源都能充分利用，提高工作效率，希望降低各个部门的成本，从而获得最大的经济利益，所以目标规划这一模型在当今时代运用得越来越广泛。对本文的物质调度问题的研究，有助于报纸、牛奶投递及线路优化，工业原材料和成品的运输，电话或网络的车辆配装及线路设计，连锁商店的送配货等等物资调动问题解决，尽可能减小成本以获得更大利润。本文由于要考虑的每一种的情况过于复杂，所以还采用了蒙特卡洛算法，也称统计模型方法，以概率统计理论为指导，通过随机数简便了本文问题的运算量，并广泛运用于金融工程学、宏观经济学、计算物理学等领域。九、参考文献1汤宇，多目标规划模型的研究，网友世界，01:52,2014。2周

25、义仓 郝孝良，数学建模实验，西安：西安交通大学出版社，1999。3雷功炎，数学建模讲义，北京：北京大学出版社，1999。4袁震东 蒋鲁敏 束金龙，数学建模简明教程，上海：华东师范大学出版社，2002。附录点与点的距离clc;close all;clear all;a=zeros(31,2);load mydata a;for i=1:31 for j=1:31 c(i,j)=sqrt(a(i,1)-a(j,1).2+(a(i,2)-a(j,2).2); endendfor i=1:30d(i,1)=sqrt(a(i,1)-a(i+1,1).2+(a(i,2)-a(i+1,2).2);end点间

26、路程矩阵clc;close all;clear all;a=zeros(31,2);load mydata a;for i=1:31 for j=1:31 c(i,j)=sqrt(a(i,1)-a(j,1).2+(a(i,2)-a(j,2).2); if(i=j) c(i,j)=0; else if(c(i,j)=10&c(i,j)=15) c(i,j)=c(i,j); end end if(abs(i-j)=1&i=j&(c(i,j)15) c(i,j)=; end endend% for i=1:30% for j=2:31% c(i,j)=sqrt(a(i,1)-a(j,1).2+(a(

27、i,2)-a(j,2).2);% end% end% for i=1:30% d(i,1)=sqrt(a(i,1)-a(i+1,1).2+(a(i,2)-a(i+1,2).2);% end01阵clc;close all;clear all;d=zeros(31,31);t=zeros(31,1);load mydatac c;for i=1:31 for j=1:31 if(c(i,j)=10)&(c(i,j)0)&(c(i,j)50 chu(m,1)=chu(i,1); chu(m,2)=chu(i,2); chu(m,3)=chu(i,3); chu(m,4)=chu(i,4)-50;

28、chu(i,4)=50; chu(i,5)=D(i,3); m=m+1; endend zhuang=chu;for i=1:100for m=1:60 for i=1:48 zhuang(i,3)=zhuang(i,3)-1; end for i=1:48 if zhuang(i,3)0); c=length(b); d=randint(1,1,1 c); zhuang(i,1)=zhuang(i,2); zhuang(i,2)=Q(zhuang(i,2),d); zhuang(i,3)=S(zhuang(i,1),zhuang(i,2); else zhuang(i,4)=0; end e

29、nd endfor i=1:48 for j=1:48 if i=j if zhuang(i,1)=zhuang(j,1)&zhuang(i,2)=zhuang(j,2) zhuang(i,3)=zhuang(i,3)+1; end if zhuang(i,4)+zhuang(j,4)50 zhuang(i,3)=zhuang(i,3)-1; end end endendx=x+1;if sum(zhuang(:,4)=0&xt t=x;end endend正态分布图clc;close all;clear all;% x = (0:0.02:10);% y = lognpdf(x,1.73,0

30、.22);% figure,subplot(121);% plot(x,y); % grid;% xlabel(x);x = (0:0.02:10);y = normpdf(x,5.0,1.4);plot(x,y,k); set(gca,xtick,xticklabel,);set(gca,ytick,yticklabel,);% grid;% xlabel(x); ylabel(p);附录表1 各仓库具体坐标位置仓库编号123横坐标40.1743.554.552纵坐标24.0916.8945.31仓库编号456横坐标19.4812.2740.54纵坐标18.085.93739.69仓库编号7

31、89横坐标21.7245.629.263纵坐标19.2712.1620.57仓库编号101112横坐标13.957.5856.319纵坐标4.9436.67547.43仓库编号131415横坐标43.4528.8527.66纵坐标47.0128.332.779仓库编号161718横坐标7.63442.4731.33纵坐标11.0317.3641.80仓库编号192021横坐标17.3525.2720.71纵坐标0.77532.0398.522仓库编号222324横坐标3.21011.296.828纵坐标32.2636.3532.53仓库编号252627横坐标9.08411.5120.85纵坐标

32、22.7227.7314.87仓库编号282930横坐标2.71145.4047.23纵坐标37.789.72334.58仓库编号31横坐标24.40纵坐标9.349表2 各仓库运输任务运输任务1运输任务2出发仓库目标仓库运输量目标仓库运输量1836.37341.7821062.901047.1331278.771766.404148.8532455.0651692.303196.2561877.02765.3172048.721442.0182243.192195.6892444.062898.02102630.57466.91112850.271133.65123051.101850.60

33、13181.622563.6614379.53177.3415564.92851.3516737.681577.7917981.772284.56181153.552947.60191335.83534.08201593.871254.78211787.841856.12221955.222665.94232162.28271.56242358.17929.89252520.281651.44262730.912389.82272947.913017.13283123.59696.2529284.891385.0930419.492069.8931622.992776.59表3 仓库之间道路距

34、离道路编号123道路距离50.48.42.道路编号456道路距离42.40.37.道路编号789道路距离36.35.33.道路编号101112道路距离30.29.28.道路编号131415道路距离26.26.25.道路编号161718道路距离25.24.23.道路编号192021道路距离22.15.15.道路编号222324道路距离14.14.14.道路编号252627道路距离14.14.14.道路编号282930道路距离14.14.14.道路编号313233道路距离14.13.13.道路编号343536道路距离13.13.13.道路编号373839道路距离13.13.13.道路编号40414

35、2道路距离13.13.13.道路编号434445道路距离13.12.12.道路编号464748道路距离12.12.12.道路编号495051道路距离12.12.12.道路编号525354道路距离12.12.12.道路编号555657道路距离12.12.12.道路编号585960道路距离12.11.11.道路编号616263道路距离11.11.11.道路编号646566道路距离11.11.11.道路编号676869道路距离11.11.10.道路编号707172道路距离10.10.10.道路编号737475道路距离10.10.10.道路编号767778道路距离10.9.8.道路编号798081道路距离8.8.7.道路编号8283道路距离6.5.专心-专注-专业