城市物流配送方案优化模型-数学建模

天津大学数学建模选拔赛题目城市物流配送方案优化设计摘要所谓物流配送就是按照用户的货物（商品）订货要求和物流配送计划，在物流配送节点进行存储、分拣、加工和配货等作业后，将配好的货物送交收货人的过程。本文就如何设计该城市的配送方案和增设新的配送网点并划分配送范围展开讨论。第一问中，首先，在设计合理的配送方案时，我们要知道评价一个配送方案的优劣需考虑哪些指标。根据层次分析法所得各指标的权重及各因素之间关系可知：合理的配送方案需要优化货车的调度以及行驶路线。然后，根据该城市的流配送网络路网信息以及客户位置及需求数据信息，用EXCEL进行数据统计并用matlab绘制物流信息图，在图中可以清晰地看出客户位置密集和稀疏的区域。之后，我们运用雷达图分割法将城市分为20个统筹区（以及100个二级子区域）。接着，我们针对一个二级子区域分析货车行驶的最佳路线。利用聚类分析和精确重心法在二级子区域N1中设置了7个卸货点，该目标区域内的用户都将在该区域的卸货点取货。我们利用图论中的Floyd算法和哈密尔顿圈模型求解往返最短路线问题，得知最短路线为1246753配送中心配送中心，最短路程为84.4332KM，最短运货用时为2.11小时。最后，根据用户位置和需货量，计算出货车数量和车次，并给出了其中一种合理的针对整个城市的货车调度配送方案。第二问中，我们建立了多韦伯模型，通过非线性0-1规划，确定了城市增加的5个分配中心的位置以及各自的分配送范围。配送中心位置结果如下：配送中心编号经度纬度3108.056801526.717164454108.67965126.96689015108.689218525.97394826109.211669326.895898637109.174977326.1636702原配送中心107.97255461516226.6060305362822关键词：层次分析法聚类分析精确重心法Floyd算法哈密尔顿圈多韦伯模型评阅编号（由组委会填写）1一．问题重述配送是指在经济合理区域范围内，根据客户要求，对物品进行拣选、加工、包装、分割、组配等作业，并按时送达指定地点的物流活动，即按用户定货要求，在配送中心或其它物流结点进行货物配备，并以最合理方式送交用户。配送是从用户利益出发、按用户要求进行的一种活动，因此，在观念上必须明确“用户第一”，把用户利益作为设计配送方案时首先要考虑的问题。城市的配送系统不但要考虑企业自身和用户的利益，也应从公众利益出发，尽量减少交通拥挤和废物排放。这无疑更增加了配送系统管理的难度，有效解决该问题对于改善城市出行环境和提高企业服务水平具有重要意义。基于以上背景，为某企业设计其配送方案，建立数学模型分析如下问题：（1）假设该公司在整个城区仅有一个配送中心（107.972554615162，26.6060305362822）。附件1中给出了企业顾客位置和需求数据。附件2为配送网络路网信息。由于顾客需求为平均量，为克服需求高峰车辆不够的情况，实际中通常对每辆车的装载量进行限制，实际载货量为规定满载量的70%。司机工作时间为每天8小时。不考虑车辆数量限制，请为企业设计合理的配送方案。（每件产品规格：长：27.5CM，宽：9CM，厚：5CM）。配送用车请参考实际货车规格自己选定。（2）适当增加配送中心数量，能降低配送成本，假设计划增设5个配送中心，请为各配送网点划分配送范围。二、问题背景和问题分析2.1问题背景所谓物流配送就是按照用户的货物（商品）订货要求和物流配送计划，在物流配送节点（仓库、商店、货物站、物流配送中心等）进行存储、分拣、加工和配货等作业后，将配好的货物送交收货人的过程，城市物流配送是指在城市范围内进行的物流配送业务活动，城市物流配送系统的服务对象归类为：政府、工业、商业、农业、大众客户。城市物流配送已随客户需求变化从“少品种、大批量、少批次、长周期”向“多品种、小批量、多批次、短周期”转变。随着中国城市化进程的进一步加快，不管是从城市经济发展，还是从城市空间结构、城市交通运输布局及城市基础设施建设来考虑，每个城市都面临一个对原有的物流配送系统进行改造、建立新的物流配送系统的问题，这就是城市物流配送系统优化提出的原因。[1]2.2问题分析对于第一问，为了得到最优的配送方案，我们着重从货车的调度和货车的行走路线进行设计。首先我们需要对城市进行分区，并设计货车在所有区域内进行统筹调度的方法。然后，我们针对某一个小的区域，运用图论的知识，寻找货车运送完全部货物的最短路线，实现用户、社会和公司总体利益的最大化。对于第二问，我们需要找到五个新增配送中心的位置并且划分各个配送网点的配送范围。这是一个典型的多韦伯问题。期间我们不但要注意使得配送中心到用户的距离之和最短。同时也要满足配送中心尽量偏重用户需求量大的地区的要求。2三、模型假设1.建立基本模型时，所有配送用车规格（小型货车）相同。2.送货时配送用车均以40KM/h的速度匀速行驶。(偏远地区交通环境良好，速度可适当提高)3..送货时无极端天气以及交通拥挤、交通事故、道路修理等影响送货的情况发生。4.不存在用户不取货以及退货的情况。5.货物在包装、囤积和运输过程中没有破损。6..基本模型中我们只要求货物在订货周期内送达即可，即达到此要求则可实现用户的满意度为满分。7.在第一问中，我们选取一个子区域进行精确分析，以其为样本估计整个城市的情况，样本具有普遍性。四、符号约定xi：用户位置的经度值。yi：用户位置的纬度值。x0：配送中心的经度值。y0：配送中心的纬度值。i，j：用户位置编号。：用户相对于配送中心的方位角。L：用户距离配送中心的距离。Dij：任意两个用户位置之间的距离。C：哈密尔顿圈。V：哈密尔顿圈中的边。M：某一区域一周之内需要的车次数。Q：某一区域一周之内的需货量。N：一辆货车每日行驶车次数。T：一辆货车行驶一个车次所需时间。W：评定配选方案是否最优的的指标。：判断矩阵A的最大特征值；IC：判断矩阵A的一致性指标；Zm:“招聘效益最大化”数值。max3五、模型的建立与求解5.1对问题一的求解问题一中，需要考虑用户需求，公司利益，环境影响等多个方面的问题，给出最佳的配送方案。5.1.1数据预处理1、我们已知，每件产品规格：长：27.5CM，宽：9CM，厚：5CM），体积为1237.5CM3。根据实际情况，我们选定货车箱为长3M，宽1.8CM，高1.8M的东风小型货车，体积为9.72M3。由题目可知实际中通常对每辆车的装载量进行限制，为规定满载量的70%，所以实际载物体积为6.804M3，可载5180箱货物。（据计算，货物合理布局后可在货车中全部安放。）2、对于表中空白数据，预先进行处理：订货周期空白默认为一周，订货量空白默认为0，订货时间空白默认为周六订货，此部分数据少，不影响最后结果。道路ID空白对结果无影响，故不考虑。5.1.2设计评定配送方案的指标倘若想要设计一个最优的配送方案，需要知道哪些指标应该重点考虑，而那些可以在基本模型中忽略。只有首先通过层次分析法[2]计算出各指标的权重，我们才能做出一个合理度较高的优化方案。一、层次分析法设定各指标权重由题意，评价一个配送方案的是否合理主要可从用户利益，公司收益，社会利益三个方面来考虑。1、用户利益主要由送货时间与“卸货点”到用户实际位置间的距离决定。*“卸货点”：货车的卸车地点，用户可以到“卸货点”来取货，多个用户可以共用一个“卸货点”。2、公司收益主要由仓库积压程度，需要拥有的车辆数，每天发出的车次数，车辆的总行驶距离即耗油数决定。3、社会利益主要由所有车辆行驶的总公里数，每天发出的车次数，动用的货车种类决定。因为这三个量会影响污染的程度和交通拥挤的程度。这是一个多目标决策问题。我们运用层次分析法确定各因素在评价方案优劣时所占的权重。具体分层如图所示：目标层准则层模型合理度评价A用户利益B1公司利益B2社会利益3到货时间C1卸货点与用户间实际距离C2仓库积压程度C3需要拥有的车辆数C4每天发出的车次数C5车辆的总行驶距离C6车辆行驶的总公里数C7每天发出的车次数C8动用的货车种类C94对同一层次的各个元素关于上一层次中某一准则的重要性进行两两比较，构造两两比较判断矩阵。在构造两两比较判断矩阵的过程中，按1～9比例标度对重要性程度进行赋值。下表给出1～9标度的含义:标度含义1表示两个元素相比，具有同样重要性3表示两个元素相比，前者比后者稍重要5表示两个元素相比，前者比后者明显重要7表示两个元素相比，前者比后者强烈重要9表示两个元素相比，前者比后者极端重要2，4，6，8表示上述相邻判断的中间值倒数若元素I和元素j的重要性之比为aij，那么元素j和元素I的重要性之比为1/aij根据上述给出的标度含义表，对于任何一个准则，几个被比较元素通过两两比较就可以得到一个判断矩阵：xnijaA（1）其中，ija就是iu与ju相对于C的重要性的比例标度。根据得到的判断矩阵，我们采用“特征根法”来求解判断矩阵中被比较元素的排序权重向量。若矩阵A的最大特征值max对应的特征向量是W，将所得到的W经归一化后就是要求的权重向量。设TknkkkkW),...,()1(12)1(1)1(1表示第1k层上1kn个元素相对于总目标的排序权重向量，用TknkjkjkjkjpppP),...,()()(2)(1)(表示第k层上kn个元素对第1k层上第j个元素为准则的排序权重向量，其中不受j元素支配的元素权重取为零。那么第k层上元素对目标的总排序)(kW为：)1()()()(2)(1)(),...,,(kkTknkkkWPWk＝（2）对于本模型依据上述的层次分析方法，计算得到如下各个层次下的判断矩阵和其对应的排序权重向量、一致性指标：5表1目标层判断矩阵合理度A用户利益B1公司收益B2社会效益B3用户利益B1157公司收益B21/512社会效益B31/71/21CI=0.0071，CR=0.012，RI=0.58,m3.0142此步骤中应注意“用户第一”的原则。表2准则层B1的判断矩阵用户利益B1取货距离C1到货时间C2取货距离C111/2到货时间C221CI=0，CR=0，RI=0,m0表3准则层B2的判断矩阵CI=0.019，CR=0.021，RI=0.9,m4.0672表4准则层B3的判断矩阵CI=0，CR=0，RI=0.58,m0表5各指标权重指标取货距离到货时间仓库存量车辆数出车次数总油耗拥挤程度出车种类总公里数W0.2343680.4687350.0115100.0271530.0443180.1053760.0271330.0271330.054273根据多层一致性指标的计算方法)1()()(1)1()()(1)()()(),...,(),...,(11kknkkknkkkkWIRIRWICICIRICRCkk(3)利用上面求得的各个层次的一致性比例，得到(3)0.0320.1CI，符合递阶层次结构在3层水平以上的所有判断具有整体满意一致性的标准，即所得的排序权重向量是合理的。公司收益B2仓库存货量C3车辆数C4出车次数C5总油耗C6仓库存货量C311/31/41/7车辆数C4311/21/4出车次数C54211/3总油耗C67431社会效益B3出车种类C7拥挤程度C8总公里数C9出车种类C7111/2车辆数C8111/2总公里数C92216二、运货方案评价指标的量化由于各评价指标单位不同，难于统一，我们采用分项计分制，并在计算总分时利用向量的单位化将单位统一，从而求得该待评价方案的总分。向量单位化的公式如下：jjjjjRRHCR（4）其中22221,jnjjjjjRRRRRR，是n维向量jR的长度。具体的评分细则如下：1、用户利益部分用户部分采用罚函数进行计算。罚函数将有约束最优化问题转化为求解无约束最优化问题:其中M为足够大的正数,起惩罚作用,称