建模题二 - 图文

2014年数学建模论文

第三套

题 目： 物流调度系统

组 别： 第3组

姓 名： 周华坤 常亚飞 杨曼

提交日期：7月10日

物流调度系统

摘要

随着市场经济的发展和物流专业化水平的提高，物流配送业得到了迅速的提高，所以如何解决物流配送车辆调度的问题就逐步成为城市建设发展的焦点。本文通过建立0-1整数规划模型，研究在不同限制条件下物流调度系统的车辆安排路线问题。

对于问题一：要使得成本最低，就要求得最短路径及最低的空载率。首先利用Floyd算法求出任意两城市间的最短距离矩阵d,并采用搜索优化算法，找出最优路径和货车运输方案，使货车利用率最大。然后以订单成本作为建模对象，建立0-1整数规划的数学模型，最后求解出给出方案的总成本。

对于问题二：这是一个多起运地多目的地的问题。首先我们整理附件二资料，得到起运地与目的地的货车车位数和该城市运单数的不同对比情况，通过改善问题一的搜索优化算法，对问题二的最优路径进行求解。然后采用问题一的建模思想，但是建模对象改为货车，同样建立0-1整数规划模型，最后求解得到最低成本。

对于问题三，首先根据货车的评级分数定义满意度p，定义问题二所得结果对应的满意度最小，建立多目标规划模型，采用主要目标法，根据题意，选择运输成本作 为主要目标，把优先安排车辆评级分数较高的货车这一目标用满意度刻画并作为次要 目标，在问题二的模型基础上主观添加满意度p?p2?120%这一约束条件，利用遗传算法进行求解。

关键字：Floyd算法 搜索优化算法 0-1规划模型

一、问题重述

随着我国经济突飞猛进的发展，物流成为社会分工中重要的环节。物流系统的优劣也影响了业务流程的运行效率及其成本。国内某家物流公司的主要业务是从分布在全国的M个主机厂，将N种品牌商品小汽车调运到全国多个城市的4S店。请为该物流公司设计一套物流运输优化系统，以提高物流运输效率、优化运营成本。

不考虑小客车类型的差异，在运输过程中产生的主要运输成本包括：运输商品小汽车的业务费为0.7元/(公里·辆)，货车运输途中因部分车位空闲而产生的空载运输成本为0.2元/(公里·车位)，油耗动力成本为0.5元/公里，货车过路费用为0.4元/公里。

问题1：建立数学模型考,虑从某个主机厂调度货车来完成运输订单，如何安排货车，可以保证在完成运输任务的基础上运输成本最低。请用附件1中的数据来验证你的模型，并根据你的结果给出运单方案。允许将不同订单用同一货车运输，但是不允许将同一订单拆分用不同货车运输；一个运力货车运单的目的地城市的数量不超过3个。说明：车位是指一个货车最多能运输小客车的数量。

问题2：由于小客车品牌不同，因此在运输的时候将小汽车进行了分级标识，级别最高的为1，在同一个起运地优先安排货车运输这些级别高的小汽车。如果货车有剩余车位，则可以顺途运输其他城市的订单；如果起运地货车数量不足，可以从附近城市调运货车来运输本地订单。请建立数学模型，考虑如何安排货车，可以保证在完成运输任务的基础上运输成本最低。结合附件2中的数据，进行求解并给出运单。

问题3：每辆货车对公司物流运输系统的价值和效率是不同的，通过对每一辆货车的运输汽车质损率、及时到达率、信息反馈率和服务态度等多方面进行跟踪评价，可以得到货车的评级分数，分数越高说明运输质量和效率越好。故在安排货车运输方案的时候，首先考虑运输成本最小，其次优先安排车辆评级分数较高的货车，在问题2的基础上，利用附件3中的数据进行求解并给出新的运单。

二、问题分析

问题一的分析：

题目要求建立数学模型完成运输订单并且安排货车保证在完成运输任务的基础上运输成本最低，因此我们的目标函数是总运输成本最低，其中会产生成本的因素包括业务费、空载运输成本、耗油成本、过路费。而货车可允许不同订单用同一货车运输不允许同一订单用不同货车运输；货车运单的目的城市不超过三个，这些即目标函数的约束条件。由于约束条件，决定了路径的选择只有三种情况，即一个目的地，两个目的地，三个目的地。要使总运输成本最低则要一方面路径最短另一方面空载率最低。首先对数据进行预处理，依照每个城市的经纬度，用matlab画出下图一，根据图一将各个城市分成6个区域，分区情况见表一。然后运用floyd算法求出任意两点之间的最短距离，找出最优路径，再通过建立0-1整形规划模型，求解得到满足约束条件下的最优解。

图1 表1：目的地分区情况表 区域 区域内城市 1 大庆市、牡丹江市、长春市、沈阳市、盘锦市、葫芦岛市 2 包头市、银川市、兰州市 3 常德市、长沙市 4 成都市、达州市、自贡市、遵义市、贵阳市、南宁市 5 商丘市、蒙城县、日照市、东营市、济南市、漯河市、郑州市、青岛市 6 金华市、龙岩市、福州市、衢州市、宁波市、三明市、杭州市、桐乡市 问题二的分析： 问题二是基于小汽车不同等级优先运输的最优化问题。问题要求我们在同一个起运地优先安排货车运输级别高的小汽车，如果货车有剩余车位，则可以顺途运输其他城市的订单；如果起运地货车数量不足，可以从附近城市调运货车来运输本地订单。在完成任务的同时保证最低成本。根据问题，我们将起运地分为6类，建立0-1规划模型求解该问题。 问题三的分析：每辆货车对公司物流运输系统的价值和效率是不同的，通过对每一辆货车的运输汽车质损率、及时到达率、信息反馈率和服务态度等多方面进行跟踪评价，可以得到货车的评级分数，分数越高说明运输质量和效率越好。故在安排货车运输方案的时候 ，首先考虑运输成本最小，其次优先安排车辆评级分数较高的货车 ，在问题2的基础上，利用附件3中的数据进行求解并给出新的运单。

三、问题假设

1、主机厂与目的地的距离是直线； 2、各个货车之间互不影响，独立工作；

3、货车到达目的地后必须把该目的地的或送完； 4、每辆货车的路线一旦确定下来，不得更改； 5、每个城市内区与区之间的距离忽略不计；

6、不考虑货车配送订单都返回起运地的运输成本；

四、变量说明

符号 D(?) R(?) dij gk gi fk 含义 距离矩阵 路径矩阵 表示第i个订单目的地到第j个订单目的地城市的最短路径距离 表示车辆的载重量 表示用户i的货物需求量 表示车位k的车位数 x号货车运送订单i后继续或不继续运送订单j X号货车运送订单i后紧接着运送或不运送订单j 货车运送订单时产生的总耗油动力成本 货车运送订单时产生的总过路费用 货车运送小汽车的总业务费用 货车空载运输成本 总的运输费用 xij yxij M、M’ N、N’ P、P’ Q、Q’ W、W’ 五、模型的建立与求解

5.1问题一模型的建立与求解： 5.1.1模型一建立的相关知识：

（1）Floyd算法求最短路径的原理---求距离矩阵的方法

(0)把带权邻接矩阵W作为距离矩阵的初值，即D(0)=(dij)???=W

(1))(1)(0)(1)1．D(1)= (dij)???，其中dij?min{dij,di(10)?d1(0j},dij是从vi到vj的只允许

以v1作为中间点的路径中最短路的长度．

(2)(1)(2)(1)1)(2)2.D(2)= (dij其中dij,?d2}d)???，?min{dij,di(2ij是从vi到vj的只允许以jv1 、 v2作为中间点的路径中最短路的长度．

(?)(?)(??1)??1)(?)3.D(?)=(dij是从vi到vj的只)???，其中dij?min{dij,di(??d?(j??1)},dij允许以v1、v2、…、v?作为中间点的路径中最短路的长度．即是从vi到vj中间可插入任何顶点的路径中最短路的长，因此D(?)即是距离矩阵． （2）Floyd算法求最短路径的原理---求路径矩阵的方法

在建立距离矩阵的同时可得到矩阵R．建立路径。R=(rij)???, rij的含义是从

本文来源：https://www.bwwdw.com/article/oghh.html