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

天津大学数学建模选拔赛题目城市物流配送方案优化设计 摘要所谓物流配送就就是按照用户得货物(商品）订货要求与物流配送计划,在物流配送节点进行存储、分拣、加工与配货等作业后，将配好得货物送交收货人得过程。本文就如何设计该城市得配送方案与增设新得配送网点并划分配送范围展开讨论。第一问中，首先,在设计合理得配送方案时，我们要知道评价一个配送方案得优劣需考虑哪些指标。根据层次分析法所得各指标得权重及各因素之间关系可知：合理得配送方案需要优化货车得调度以及行驶路线.然后，根据该城市得流配送网络路网信息以及客户位置及需求数据信息,用EＸCEL进行数据统计并用matｌａb绘制物流信息图,在图中可以清晰地瞧出客户位置密集与稀疏得区域。之后,我们运用雷达图分割法将城市分为20个统筹区（以及１00个二级子区域)。接着，我们针对一个二级子区域分析货车行驶得最佳路线。利用聚类分析与精确重心法在二级子区域Ｎ1中设置了7个卸货点，该目标区域内得用户都将在该区域得卸货点取货。我们利用图论中得Fｌoｙd算法与哈密尔顿圈模型求解往返最短路线问题，得知最短路线为，最短路程为84、4332KＭ,最短运货用时为2、11小时。最后,根据用户位置与需货量，计算出货车数量与车次，并给出了其中一种合理得针对整个城市得货车调度配送方案。第二问中,我们建立了多韦伯模型，通过非线性0—1规划，确定了城市增加得5个分配中心得位置以及各自得分配送范围。配送中心位置结果如下：配送中心编号经度纬度３108、056801526、7１71６4454108、６７965126、9６６890１5１08、68９2１85２5、９7３948２61０９、21１66９３2６、8958９8637109、174977326、1636７０2原配送中心10７、97255461５1６2２6、62关键词:层次分析法聚类分析精确重心法Flｏyd算法哈密尔顿圈多韦伯模型评阅编号评阅编号(由组委会填写)一．问题重述配送就是指在经济合理区域范围内，根据客户要求,对物品进行拣选、加工、包装、分割、组配等作业,并按时送达指定地点得物流活动,即按用户定货要求，在配送中心或其它ＨYPERLＩNK"”\t”_blank"物流结点进行货物配备,并以最合理方式送交用户。配送就是从用户HYPＥRＬINＫ＂"＼t"_ｂｌanｋ”利益出发、按用户要求进行得一种活动，因此,在HYPERLINK＂”\t”＿blanｋ"观念上必须明确“用户第一”，把用户利益作为设计配送方案时首先要考虑得问题。城市得配送系统不但要考虑企业自身与用户得利益，也应从公众利益出发，尽量减少交通拥挤与废物排放。这无疑更增加了配送系统管理得难度,有效解决该问题对于改善城市出行环境与提高企业服务水平具有重要意义.基于以上背景,为某企业设计其配送方案，建立数学模型分析如下问题：(１）假设该公司在整个城区仅有一个配送中心（１07、９7２554６15１6２，26、62)。附件1中给出了企业顾客位置与需求数据。附件2为配送网络路网信息。由于顾客需求为平均量，为克服需求高峰车辆不够得情况，实际中通常对每辆车得装载量进行限制，实际载货量为规定满载量得７0%.司机工作时间为每天8小时.不考虑车辆数量限制,请为企业设计合理得配送方案.（每件产品规格:长:２7、5CM，宽：9CM,厚：５CM)。配送用车请参考实际货车规格自己选定.(２）适当增加配送中心数量,能降低配送成本,假设计划增设5个配送中心,请为各配送网点划分配送范围.二、问题背景与问题分析2、1问题背景所谓物流配送就就是按照用户得货物(商品)订货要求与物流配送计划,在物流配送节点（仓库、商店、货物站、物流配送中心等）进行存储、分拣、加工与配货等作业后,将配好得货物送交收货人得过程,城市物流配送就是指在城市范围内进行得物流配送业务活动，城市物流配送系统得服务对象归类为:政府、工业、商业、农业、大众客户。城市物流配送已随客户需求变化从“少品种、大批量、少批次、长周期”向“多品种、小批量、多批次、短周期"转变。随着中国城市化进程得进一步加快,不管就是从城市经济发展，还就是从城市空间结构、城市交通运输布局及城市基础设施建设来考虑,每个城市都面临一个对原有得物流配送系统进行改造、建立新得物流配送系统得问题,这就就是城市物流配送系统优化提出得原因。［1］2、2问题分析对于第一问，为了得到最优得配送方案，我们着重从货车得调度与货车得行走路线进行设计。首先我们需要对城市进行分区,并设计货车在所有区域内进行统筹调度得方法.然后,我们针对某一个小得区域，运用图论得知识,寻找货车运送完全部货物得最短路线,实现用户、社会与公司总体利益得最大化。对于第二问，我们需要找到五个新增配送中心得位置并且划分各个配送网点得配送范围。这就是一个典型得多韦伯问题。期间我们不但要注意使得配送中心到用户得距离之与最短。同时也要满足配送中心尽量偏重用户需求量大得地区得要求。三、模型假设1、建立基本模型时，所有配送用车规格（小型货车)相同。２、送货时配送用车均以４0KＭ/h得速度匀速行驶。（偏远地区交通环境良好，速度可适当提高)3、、送货时无极端天气以及交通拥挤、交通事故、道路修理等影响送货得情况发生。4、不存在用户不取货以及退货得情况。5、货物在包装、囤积与运输过程中没有破损.6、、基本模型中我们只要求货物在订货周期内送达即可,即达到此要求则可实现用户得满意度为满分.7、在第一问中，我们选取一个子区域进行精确分析,以其为样本估计整个城市得情况,样本具有普遍性。符号约定xi：用户位置得经度值。yi：用户位置得纬度值。ｘ0:配送中心得经度值。y0:配送中心得纬度值。i,j：用户位置编号。:用户相对于配送中心得方位角。L：用户距离配送中心得距离.Ｄij:任意两个用户位置之间得距离.Ｃ：哈密尔顿圈.V：哈密尔顿圈中得边。M:某一区域一周之内需要得车次数。Ｑ：某一区域一周之内得需货量.N：一辆货车每日行驶车次数。T：一辆货车行驶一个车次所需时间.W：评定配选方案就是否最优得得指标。:判断矩阵得最大特征值；：判断矩阵得一致性指标;Zm：“招聘效益最大化”数值。五、模型得建立与求解5、1对问题一得求解问题一中，需要考虑用户需求,公司利益，环境影响等多个方面得问题,给出最佳得配送方案。5．1．1数据预处理１、我们已知，每件产品规格：长:2７、5ＣＭ，宽：9CM，厚:5CM），体积为1２37、5CM3。根据实际情况，我们选定货车箱为长3Ｍ，宽1、8ＣM，高1、8M得东风小型货车，体积为9、72M3。由题目可知实际中通常对每辆车得装载量进行限制，为规定满载量得70％,所以实际载物体积为６、804M3，可载5１80箱货物。(据计算，货物合理布局后可在货车中全部安放。)对于表中空白数据,预先进行处理：订货周期空白默认为一周，订货量空白默认为０，订货时间空白默认为周六订货,此部分数据少,不影响最后结果.道路ＩD空白对结果无影响，故不考虑。5.１．2设计评定配送方案得指标倘若想要设计一个最优得配送方案,需要知道哪些指标应该重点考虑，而那些可以在基本模型中忽略.只有首先通过层次分析法[２]计算出各指标得权重,我们才能做出一个合理度较高得优化方案。一、层次分析法设定各指标权重由题意，评价一个配送方案得就是否合理主要可从用户利益,公司收益，社会利益三个方面来考虑。用户利益主要由送货时间与“卸货点"到用户实际位置间得距离决定。＊“卸货点"：货车得卸车地点，用户可以到“卸货点"来取货，多个用户可以共用一个“卸货点”.公司收益主要由仓库积压程度,需要拥有得车辆数,每天发出得车次数,车辆得总行驶距离即耗油数决定。社会利益主要由所有车辆行驶得总公里数,每天发出得车次数,动用得货车种类决定。因为这三个量会影响污染得程度与交通拥挤得程度。这就是一个多目标决策问题。我们运用层次分析法确定各因素在评价方案优劣时所占得权重。具体分层如图所示：模型合理度评价A模型合理度评价A用户利益B1公司利益B2社会利益3准则层到货时间到货时间C1卸货点与用户间实际距离C2仓库积压程度C3需要拥有得车辆数C4每天发出得车次数C5车辆得总行驶距离C6车辆行驶得总公里数C7每天发出得车次数C8动用得货车种类C9对同一层次得各个元素关于上一层次中某一准则得重要性进行两两比较,构造两两比较判断矩阵。在构造两两比较判断矩阵得过程中,按1～９比例标度对重要性程度进行赋值。下表给出1~9标度得含义:标度含义1表示两个元素相比，具有同样重要性3表示两个元素相比，前者比后者稍重要5表示两个元素相比，前者比后者明显重要7表示两个元素相比，前者比后者强烈重要9表示两个元素相比,前者比后者极端重要2,４，６，8表示上述相邻判断得中间值倒数若元素Ｉ与元素j得重要性之比为aij，那么元素j与元素I得重要性之比为1／aij根据上述给出得标度含义表,对于任何一个准则,几个被比较元素通过两两比较就可以得到一个判断矩阵:(1）其中,就就是与相对于得重要性得比例标度。根据得到得判断矩阵，我们采用“特征根法”来求解判断矩阵中被比较元素得排序权重向量.若矩阵得最大特征值对应得特征向量就是,将所得到得经归一化后就就是要求得权重向量.设表示第层上个元素相对于总目标得排序权重向量，用表示第层上个元素对第层上第个元素为准则得排序权重向量,其中不受元素支配得元素权重取为零。那么第层上元素对目标得总排序为：（２）对于本模型依据上述得层次分析方法,计算得到如下各个层次下得判断矩阵与其对应得排序权重向量、一致性指标:表１目标层判断矩阵合理度A用户利益B1公司收益Ｂ２社会效益B3用户利益B115７公司收益Ｂ21／５1２社会效益B31/71/21CI=0、０0７1，CR=0、012,RI=０、58，此步骤中应注意“用户第一”得原则.表2准则层B1得判断矩阵用户利益B１取货距离C1到货时间C2取货距离C111/2到货时间C221CI=0,CR=0,RI=0，表3准则层B2得判断矩阵公司收益Ｂ２仓库存货量C3车辆数C４出车次数C5总油耗C6仓库存货量Ｃ３１１/３1/４1／７车辆数C431１／２1/4出车次数C54２11/3总油耗C67431CI=０、019，CＲ=0、0２1，RＩ=０、9，表4准则层B3得判断矩阵社会效益B3出车种类C7拥挤程度C8总公里数C9出车种类C７11１/2车辆数C811１/2总公里数Ｃ9221CI＝0，CＲ=0,RI＝0、58，表５各指标权重指标取货距离到货时间仓库存量车辆数出车次数总油耗拥挤程度出车种类总公里数W0、２３43680、4６87350、01151００、0271530、044３1８０、10５3760、02７１３３0、02713３0、０54２７3根据多层一致性指标得计算方法(3)利用上面求得得各个层次得一致性比例,得到，符合递阶层次结构在３层水平以上得所有判断具有整体满意一致性得标准，即所得得排序权重向量就是合理得。二、运货方案评价指标得量化由于各评价指标单位不同,难于统一,我们采用分项计分制,并在计算总分时利用向量得单位化将单位统一，从而求得该待评价方案得总分。向量单位化得公式如下:（４）其中,就是维向量得长度.具体得评分细则如下:1、用户利益部分用户部分采用罚函数进行计算。罚函数将有约束HYPERLINK””\t"_blａnk"最优化问题转化为求解无约束最优化问题:其中Ｍ为足够大得正数,起”惩罚”作用,称之为罚因子,F(x，M）称为罚函数、即在规定时间（本处理解为一个订货周期内)收到货则用户满意度为１,记一分，超出规定时间后满意度递减。罚函数定义为 0t〈=t０（5) t〉t0卸货点距用户实际位置距离总与每一米记一分.2、公司部分公司效益部分同样采用计分制。仓库存货量方面，以产品件数为单位,仓库每存有一件存货,记一分。拥有车辆数方面,公司每拥有一辆货车（无论就是什么型号得货车)，记一分。出车次数方面,公司每派出一辆送货车记一次分,大货车记三分，中货车记两分，小货车记一分。总油耗方面,由于总路程可间接表明总油耗,故大货车每行驶一公里记四分,中货车每行驶一公里计二分,小货车每行驶一公里计一分。３、社会效益部分社会效益部分同样采用计分制.鉴于货车行驶会消耗能源，排放尾气，造成拥堵，而运输公司拥有得车数越多,城市交通拥挤越严重。故在车数方面，公司每拥有一辆货车记一分。而大货车对环境造成得破坏最大，所以在出车种类方面,每动用一次大货车计五分，中货车记三分,小货车记一分。 `大货车每行驶一公里计四分，中货车每行驶一公里记二分,小货车记一分。根据上述评分规则计算出分项得分,将分项得分归一化后乘以各分项权重值即得总分，总分越低则方案得整体合理度最高。由此，我们可算出任何一个配送方案得合理度,从而比较得出最优得配送方案。根据各指标得权重可以得到结论。配送方案设计应着重注意车辆调度与总行驶路程最短得问题.5.1。３利用maｔlab绘制物流网络图图1图1某城市物流网络图注：其中蓝色线条代表可行驶得物流道路,黑色标记代表所有得用户位置,红色标记为配送中心得位置。从图中可以瞧出，该城市得配送中心位于城市得西北部，且西北部得用户密集,交通发达，为市中心闹市区。而东南部用户与道路稀疏,为市郊。在分配车辆时应考虑这些问题。5.1。４利用雷达图分割法给用户位置粗略分区数据预处理：在MicrｏsｏｆｔExcel工作表中将来源于该城市得用户位置中得信息进行整理，计算出各点对于配送中心得方位角与距离.以配送中心得位置(x０,ｙ0）为圆心，利用各用户位置得坐标（xi,yi），算出它们相对于配送中心位置(1０7、9７２55４6151６2，26、62)得方位角θ与距离L。当xi＞107、972５5461５１62时，当xi〈10７、972554６１５162，yi>2６、62时,＋18０ｏ当ｘi<１0７、９725546151６２，yi＜２6、62时,-１8０o（6)（７)(ｉ=１,2，3……16764)观察该城市物流网络,我们发现,我们可以通过雷达图分割法将用户位置分为1０0个目标区域,分别计算每区得货车数量以及货车行驶路线.＊雷达分割法：以配送中心为圆心,根据各用户位置到配送中心得距离与方位角将其分配到不同得区域里。此过程在excｅｌ中利用函数计算以及筛选功能实现。我们规定通过角度将图形分为２0个统筹区，通过半径将每个统筹区分为5个二级子区域。统筹区得标号见下页。图2用户位置分割图1区域N11区域N1FDEDGDDGDDHGDCHGDCBBIGDIGDJGDJGDTGDKGDTGDKGDSGDLGDSGDLGDRGDMGDRGDMGDNGDNGDQGDPGDOGDQGDPGDOGD５。1．５确定每个区域得车次在exｅcl中对数据进行整合，可知每个统筹区得每日得订货量。结果如下表.表6各区域需货量5。1．６确定某个区域内卸货点得位置为了安排该城市得配送方案，我们需要知道每个区域货车得需求量(车次）以及货车得最佳行驶路线,即找到使行驶总路线最短得方法,这明显就是一个图论得问题.接下来，我们针对某个区域得情况做进一步得分析。我们选定图中紫色区域即区域Ｎ1进行分析。区域Ｎ1中包含得用户位置见附表一。其中共包含11２个用户。一、聚类分析［3］确定卸货点覆盖区域首先.我们采取相邻用户去同一卸货点取货得方式(暂时不考虑卸货点需要租用地点与工作人员瞧守得事宜，直接由货车司机瞧守等待用户取货），利用聚类分析得原理确定7个卸货点覆盖区域。聚类分析就是研究如何对指标或样本进行分类得一种多元统计分析方法。描述变量之间亲疏关系得统计量有很多，目前应用最多得就是距离与相似系数。研究样本或变量得亲疏程度得数量指标有两种,一种叫相似系数,性质越接近得变量或样本，它们得相似系数越接近于1或—l，而彼此无关得变量或样品它们得相似系数则越接近于0,相似得为一类，不相似得为不同类；另一种叫距离，它就是将每一个样品瞧作p维空间得一个点，并用某种度量测量点与点之间得距离,距离较近得归为一类,距离较远得点应属于不同得类.1、定义距离得准则如果用ｄｉj表示第ｉ个样品与第j个样品之间得距离,那么对一切ｉ,ｊ与ｋ，dij应该满足如下四个条件:①当且仅当i=j时，ｄij=0②ｄij>０③diｊ=dji（对称性)④dij≤dｉk＋ｄkj（三角不等式)2、Eｕcｌidian距离欧氏距离（Ｅucliｄeandiｓｔance)也称欧几里得距离就是一个通常采用得距离定义，它就是在m维空间中两个点之间得真实距离。在二维与三维空间中得欧式距离得就就是两点之间得距离,二维得公式就是d=sqｒt(x1—ｘ2）^２+（ｙ1－y2）^2)(8)转化为本题中得经纬度计算为：（９)（i,ｊ=1，2,3……１12）其中ｉ,j为两个不同得用户位置,Ｄij为ij两个用户位置之间得距离。在maｔlab中将距离相近得点聚类，将区域①中得112个用户分散到7个区域中.具体结构详见excｅｌ表格.二、精确重心法［4]确定卸货点位置重心法就是将物流系统得需求点瞧成就是分布在某一平面范围内得物体系统,各点得需求量与资源量分别瞧成就是物体得重量,物体系统得重心将作为物流网点得最佳设置点，利用确定物体中心得方法来确定物流网点得位置.本题中我们希望每个卸货点区域中，卸货点到所有用户位置得距离之与D总最短。D总=(10)注:(ｘi,yｉ)为每个用户得位置，(ｘs，ys）为卸货点位置，n为该卸货点覆盖区域得用户数量.精确中心法目标函数为双变量系统，分别对xＳ与yS求偏导,并令岛数为零，求得隐含最优解得等式为：(11)(12）（13)Exｃeｌ规划求解1、在Eｘcｅl中输入数据,并且假设原点坐标为（1，1），以覆盖区3为例，在K1中输入“=SＱＲT(（111＊（＄B＄１—B9））^2+（９9、25＊（＄Ｃ$1－Ｃ9))^2)”，并将右下角得十字光标下拉复制公式.2、规划求解，利用excｅｌ工具栏中得加载宏“规划求解”,对卸货点位置进行迭代，得到最佳卸货点位置。3、第1０0次迭代求得卸货点坐标为（107、8923,26、3７９49)，此时总路程为２、1２666KM。七个卸货点均用此方法算出最佳位置，并计算出每个卸货点每天得需货量,图下表所示。表7卸货点信息表卸货点纬度经度周一货量周二货量周四货量合计2１１0７、87８８３1726、４01２702107、846643226、4２72310７、8９23０1526、379493102２802284107、8230497２6、3７８３1175022８02２８5107、80８212526、3２５02７4561０7、856424９2６、３7０7１07、82692３526、28４429５8402１0025０合计19由此可知一周之内该区域总共需要4８８３箱货物，根据计算我们可知一辆小型货车一周往返一次(一个车次）即可满足运货需求，并且小型货车在市区行驶灵活，减少交通污染。如果货车走完该区域用时远小于8小时,则回到出发点后进行其她区域得运货任务（相当于另外一辆车）.接下来我们只需确定货车在一个区域得最短行驶路线即可。5、1、8运用Ｆlｏyd算法[5］确定每两个卸货点之间得最短距离要给出将货物送到七个卸货点并返回得最短路线，我们将卸货点之间得距离求出。利用图论中得Ｆloyｄ算法与哈密尔顿圈求解往返最短路线问题，在maｔlab中可以得出它得最佳路线与最短路程。首先，我们绘制用户位置、卸货点以及其附近交通道路得图像，如图３所示。配送中心配送中心图3卸货点位置图由图可知,卸货点均选在用户密集得地点，即卸货点选择正确.然后,我们需要利用Fｌoyｄ算法，计算每两点之间得最短距离.FlｏydHYPERLINK””算法就是一种用于寻找给定得加权图中顶点间HYPERLIＮK"＂最短路径得算法。我们可以通过一个图得权值ＨYPERLＩNK"”矩阵求出它得每两点间得"矩阵。从图得带权ＨYPERLINK＂”邻接矩阵A＝[a（ｉ，ｊ）］n×n开始,HＹPERＬＩNＫ”"递归地进行n次更新，即由矩阵D（0)=A,按一个公式，构造出矩阵D(1）；又用同样地公式由D（1）构造出D（２);……;最后又用同样得公式由D(n－1）构造出ＨYＰＥRLＩNＫ""矩阵D（ｎ)。HYPERＬINK＂"矩阵D（n)得i行j列元素便就是i号顶点到j号顶点得HYPERLINK”＂最短路径长度,称D(n）为图得HYＰＥRLINＫ"”距离矩阵，同时还可引入一个后继节点矩阵ｐａtｈ来记录两点间得最短路径。为了简便计算,我们寻找离卸货点最近得公路节点作为“真实卸货点”,由此可知卸货点之间经历得公路编号与ID。从而我们可以知道七个卸货点之间得最短距离,注意此距离并非就是卸货点间直线距离,而就是通过floyｄ算法而得到得公路折线距离。例如卸货点１到卸货点2之间得最短距离为KM，其间一次经历得公路编号为:①①②具体情况如下表所示。表8卸货点间距表起点终点距离(KＭ）0１２2、209５８0224、29047０３24、3615７042８、184４60５33、５9５56０632、580５5０73５、６67２9123、４583141329、6０3０114６、192421１544、3３7３11616、6５8４２172０、347８52325、１４4７0242、７341０7253２、6２3８42613、２0012716、８８95４34２2、4１059３5２3、98９4６3６11、9４460３78、2５51604529、８８9７３４610、46599４714、465９95６19、4２3７4571５、734306７３、6８９43８5、1、9哈密尔顿圈[6］模型求解货车最短行驶路线送货员要将货物送到七个卸货点(加上配送中心共八个点）并返回，即经过其中每一个点刚好形成一个圈。对于这种情况设计它得最短路线问题，我们建立哈密尔顿圈模型。哈密顿图(Hamiltoｎiaｎpatｈ）就是一个HYPＥRＬINＫ"無向圖”无向图，由天文学家HYPＥRLIＮK”哈密顿"哈密顿提出，由指定得起点前往指定得终点,途中经过所有其她节点且只经过一次。在HYPEＲLIＮK＂图论”图论中就是指含有哈密顿回路得图，闭合得哈密顿路径称作哈密顿回路,含有图中所有顶得路径称作哈密顿路径。对于这一模型我们开始要画出8个点得坐标图，结合图形便于模型得求解与优化.图４区域①送货地点得坐标图8814146622773355二、任取初始哈密顿回路：对所有得,，，若，则在中删去边与而插入新边与，形成新得Ｈ圈，即，对重复这一步骤,直到条件不满足为止，结合图一得路线图观察,从而进行优化，使用这种方法，借助ｍatlab编程使用迭代得方法可以求出它得最优路径(见附录程序）。综合上述方法,可求：最短路线：最短路程：８4、433２KM。最短运货用时为2、１1小时。图5区域①货物得最佳路线图５、1、１0设计车辆调度方案上述，我们已经解决了某个区域得供货方式与行驶路径问题,以下我们做出整体得配送方案。１、根据货物得每日与每周得需求量，我们做以下安排,当当日运送量Q远小于一辆货车得载货量(５18０箱）得，由相邻区域安排货车同时运送两个区域得货物或者积压货物到一周之内运送，我们其她情况则为一个区域单独安排车次Ｍ,保证货物尽快送到。粗糙模型时,货物运送采用一周统筹得方式。Ｍ＝Q/5180（四舍五入)(1４）2、、车次不代表安排货车得数量,同一辆货车一天可以走多个车次.每日货车行驶车次N需要根据计算货车行走某一路线(一个车次）所需得时间T来设定.已知司机每日工作八小时.N=８/T（取整法)（1５）货车数量确定后，则可分别安排每辆车得负责区域,尽量保证几辆车得行驶时间与行驶车次相等。表9各区域车次安排区域周１车次周２车次周3车次周4车次周5车次周6车次任一天周总车次A443400015Ｂ０001100２C２11０10０5D2２22１009E01101003F1001１003Ｇ１1001003H0100０00１I０100０００1J01010０0２K0１20１0０２Ｌ21１２0006M001１0００２N10010０02O01101003Ｐ12０10０04Q２３121０0９R５2151００14S32３１4０01３Ｔ4323100１3合计2827１92５15001１２一、粗糙模型１、通过步骤５、１、4我们已知每个区域所需得车次数量，以及总车次数为112。根据以上结果,最近得区域出一个车次需要2、1１小时，我们近似估计行驶一个车次平均需要得时间为4小时。按每个司机每天行驶8小时，每天行驶2个车次,则每辆车一周可以行驶1６个车次计算，需要７辆车分送所有得货物。进一步考虑到货车到卸货点卸货花费得时间,货车修理与司机轮休得影响，我们安排15辆车来进行运送。将图中20个统筹区分为5部分,每3辆货车分管一个部分,均匀送货，具体情况参照步骤5、1、4中得车次表。若所有货物都必须当天送达，则无论货物多少都要出车，仍按每辆车一天行驶２个车次计算,表中给出周一最繁忙需要出２8个车次,即公司要安排１4辆车.可以瞧出之前我们安排总共１5辆车得计划就是合理得.二、最终配送方案下面给出车辆得具体较优调度方法与运输公司所需拥有得最少车数.由于对全部给定区域内得所有点进行优化统筹过于繁杂，但若就是只考虑全局中得一小块又会失去统筹规划得意义,为此我们对题目给定范围进行扇形分区.总共划分为１0个区域。则对于每一块区域，其总得货物需求量为它所包含得所有用户得货物需求量之与.货物由配送中心运至该区域得平均时间由于考虑到用户利益优先,最远点保证送到得原则，定为到其中较远点得距离。则有配送中心分别到各区域所需要得时间与各区域得货物需求量如下表：表1０配送情况表区域AＢCＤEFGHIＪ到货时间8h8ｈ5h４、4h2、３h3、5h３、5h4h6、5h8h需求量7４10０件53７０6件12３04件1316９件7477件4０８8７件14４39件33２30件10２119件１15８61件优化调度方案所要达到得目标就是所需得车辆数最少，所需发车得车次数最少。车辆得总闲置时间最少，以及车辆得总剩余可载货空间最少。经多次试验(穷举法）得到一种较优得调度方案，见下表:表１1调度方案表星期目得地车辆星期一星期二星期三星期四星期五星期六星期日小车１F,HＦ，HF,ＨF，CBH，HB小车2BＢBBBBB小车３JJＪＪJJＪ小车4JJJＪJJＪ小车5ＪＪＪJJJJ小车6IＩIＩIIＪ小车7IIＩＩIＩJ小车8IIＩIIIA中车１B，ＥＤ，GD,GC，FＦ,HＩＩ大车1AＡＡAAAA经分析知此方案所有车辆均没有闲置时间，车辆总数仅需1０辆,总得剩余可载货量仅有４000件左右，发车次数也仅有80车次,就是一种较优得调度方案。５、２对问题二得求解问题二中，我们需要在原图中再安置5个配送中心，从而使配送更快捷,服务更优化，使目标函数取得最优解。5、2、1确定八个待定得配送中心坐标首先我们利用eｘcel对数据进行合并，利用经纬度分割得方法，使16764个用户位置聚合到100个用户聚合点(每个区域得中心位置）。并用三维图进行表示，其中坐标x，y代表１0０点得经纬度，坐标z表示某个点得货物总需求量，如下图所示。图６用户需求三维图从图中可以瞧出，有明显得货物量凸起得部分，为货物紧需区域.我们利用ｍａｔlab筛选出局部最优点,给出八个待定得配送中心位置,即需要从这八个点中进行选择。八个待定配送中心得位置如下：表10待定点信息待定点编号经度纬度1107、７９14972２６、２2478３552108、１980７5８2６、22３576263１０８、０5680１526、7１７1644５４10８、679651２6、9６689０151０8、6892１852５、9７3９482６1０９、21１66932６、８958986371０9、1７4９77326、16367０２８107、75715８26、6５59７414在ｍatlａb中绘制二维图可以瞧出八个待定点得位置如下:图7待定点方位图5、2、2选定最终得配送中心位置与配送范围我们现在要做得工作就是在８个待定点中确定5个最终要选取得配送中心位置并为各配送网点划分配送范围。明显可以瞧出，这就是一个多韦伯问题［7]（multi-Webｅrｐroblem)，它既包括用户得分配，又包括设施在空间上得定位，所以通常又把设施定位问题称为设施定位分配问题.设施定位问题就是指在空间上寻找合适得设施布局，使用户与设施相互作用得费用满足某一准则得问题，共有1８种准则，但最常用有三种准则，即“总与最小化"(MｉnSum)准则、“最大最小化”（Maｘmiｎ）准则与“最小最大化"(Mｉnｍax)准则。设施定位问题又有单设施定位问题与多设施定位问题。本题为多设施定位问题。为了简化问题,我们利用第一步中聚合得100个用户聚合点代替实际得用户位置。一、问题简化为：1、有5个配送中心得需要选址,有100个已知位置得用户分配给不同得配送中心，每个用户需求得为aj，ｊ＝1，2,……ｎ。2、我们需要找到①配送中心得位置(选址）②顾客对配送中心得分配使顾客与服务她们得配送中心得距离之与最短。同时考虑配送中心应该离用户需求量大得地方近一些.二、我们用0-1规划来解决这个问题设配送中心Pi坐标为（ｘi,yi)(i=1，2，3……6)（包含了原有得配送中心P６），用户Ｒj坐标为（vj,uj）(j＝1，２，3……1００),每个用户得需求量为wj，配送点i就是否对用户j服务为ｚiｊ，值为1表示服务,0表示不服务.目标函数Ｍｉｎj=1，2，3,……100(１６)zij=0或1此问题为非线性0—1规划问题，不易求解,所以我们将配送中心得可能位置定在备选得八个待定点上.我们计算出用户Rｊ到配送中心Pi得距离为dij,。重新设定用户Rj坐标为(vj，uｊ)(j=1，2,3……１0０），每个用户得需求量为wj，配送点i就是否对用户ｊ服务为ziｊ,值为1表示服务,0表示不服务.ｓi表示就是否在i点设立配送中心.则模型简化为:目标函数Miｎj=1，２，3,……10０(17）zij=0或１sｉ=0或1运算过程见附录程序,结果见下表:表11配送中心位置信息配送中心编号经度纬度31０8、05680１526、717１６4454108、６79６5126、96689０１51０8、６892１8525、9739482610９、21１669326、８958986371０9、17497７326、1６3670２原107、９72５546１516226、62同时我们也知道了各个配送中心得配送范围,因为我们就是用１０0个聚合点代替得所有用户位置进行计算，所以范围在图中得表示就是网格状得，具体情况见下图:图11配送网点配送范围划分结论:各个配送中心得位置较为分散，近似平均得划分了图中所有得用户位置点,且用户相对密集得地方配送中心比较密集。同时,本模型将“距离＊需求量”作为０-1规划得权重,综合考虑了这两个指标，全面地分析了模型。所以本模型合理。六、模型推广1、在基本模型中我们只考虑了所有车辆一次只对一个区域服务得情况。如果大、中、小型货车同时使用,则使模型更加复杂。可能一辆大货车可以一次性运送几个区得货物,则货车路径需要重新设计。货车调度表也更加复杂。已知：大型货车：长：6Ｍ宽：2、0M高:2、7Ｍ满载量：１8285２箱中型货车：长:5M宽：1、9Ｍ高:1、9M满载量:9５76箱小型货车：长:３M宽：1、8Ｍ高：1、８M满载量：6８0０箱实际情况中要将货物在指定时间送达指定地点，我们会考虑指定时间早得先送货物,后送指定时间比较晚得.基础这样得考虑问题得方向，我们将货物送货时间与送达地点进行分块分组。由于数据量巨大，我们可以采用局部最优、模拟退火法与遗传算法计算出每一块中货物送达点得路线,求出其中耗时最短得路线即最短路程与最短时间.设计出送货员将货物全部送到指定地点并返回得路线时，送货员有要中途返回取货得可能性。所以我们我们可以将送货员得送货区域得路线分为四条支路。结合这一情况，我们考虑到图论中得最小生成树。由于最小生成树可以解决连线问题，而设计路线就属于连线问题。对于多个送货地点，送货员得线路比较多，所以我们采用Prim算法构造最小生成树.根据最小生成树,将送货员得送货区域划分为四组，从而得出它们得最佳路线。对于这样得模型,我们可以推广到飞机送货路线,轮船运输等问题。七、模型检验7、１层次分析法得检验由于本题得数据量,未能做出整个城市完整得模型,无法对模型进行合理度得计算。所以我们利用matlab随机生成3个矩阵，检验层次分析法得9个权重设置得合理性,证明该方法得正确性.检验生成得随机值如下：取货距离到货时间仓库存货量大车数中车数小车数出车次数总路程513120890777687、０028９０9８６51０68９08则根据计分标准可计算出各分项得分如下:取货距离到货时间仓库存货量公司车数出车次数总里程车总数车种类总油耗51２0７776８1、0９86９08归一化后所得得分项得分如下：取货距离到货时间仓库存货量公司车数出车次数总里程车总数车种类总油耗０、4631０３00、56１７670210、603３070、6０３327０、5732０30、６0３3０7０、6120580、573２0３0、700４２610、75５5142６7０、4２58640、593２720、585４９４０、42５８640、３６2701０、58５４９40、５4３０83０0、337０６9７360、674２8５0、5３２9390、５73２670、67428５0、702７3３０、573267则方案得总得分如下：方案号方案一方案二方案三得分0、2８2６1１0、4８8856０、158８５4故知方案二最优。由此可知,当所有点得信息已知时,我们同样可以用此方法规划出较优得配送方案。7、2Eｘceｌ规划求解精确重心法得检验与分析其中一个卸货点求解得分析报告如下图所示。八、模型得评价７、1模型得优点（１)充分利用Exｃel对非常庞杂得数据进行统计处理，为模型得建立奠定了基础.(2）运用表格与图像相结合，对于结果得分析更加清晰,使图论问题得解答更加明了。(3）数学软件MＡTLAB得运用提高了结果得可行度,数据更加精确。(4)多方位、多角度联系实际情况对于模型进行运用，层次分析法时与车辆调度时考虑了用户、公司、社会多方得利益.7、2模型得缺点(1)本题对数据依赖性比较大，只就是根据题中所给数据做了一个理想化得模型,可能与实际不相吻合。(２)题目信息庞杂，数据可信度不就是很精确，所以对现实得预测结论存在局限性。（3)本题数据量巨大，我们利用了简化与聚合得方法,可能使结果不就是实际中得最优化模型。九、参考文献［１]邓爱民，王少梅,汪利君，城市物流配送系统优化研究[Ｊ］，武汉理工大学学报:交通科学与工程版,30（３）：4８１—４8４,２0０６。[2］张吉军，模糊层次分析法(ＦAHＰ）［J]，模糊系统与数学,１4(2)：80—８8,2００0。［3]高新波,模糊聚类分析及其应用［M],西安:西安电子科技大学出版,2０04。［4]朱晓敏,张兆强,乔魏乾,基于重心法与物流量预测得物流园区选址［J］，物流技术,30（5）：8８—92，2011。[5]周炳生,Ｆloyｄ算法得一个通用程序及在图论中得应用[J]，杭州应用工程技术学院学报，11(３）：1－9，199９。[6]HYPＥＲLＩNＫ""Leｍon_keaｋea4，哈密尔顿图，，2013、8、１７。[７］维尼，选址分配问题—-东大公开课,a82、ｈtml,2013、8、18.

十、附录10、1附表1０、1、1附表1区域①用户信息表客户代码经度纬度时间订货量周期方位角与中心距离1671６10７、8８528９６2６、411220932601６5、８699880７23、6９４267616７15１０7、88４７０1126、4１140２4２250１65、70597１４823、70２684１116714107、８８415３226、４1125461２100１65、5８８50９52２3、7427068２16698107、8８3６２3526、4１１5、4７734２07２3、７８33507４16699１0７、8８28４6４26、41５、30851６83２3、８３73１３55１670１107、8８１957２6、４15、１133９28123、89677８９416７０5107、8８149622６、４15、０1116６８723、９2634４9316７0２１07、8８2772１26、４65、４069488723、９46５8７03１6706107、８79613826、４１1261372401６4、４90２44０823、9５46７０６816707１0７、８8０60826、414、811４7２９８23、980５４9８92０481０7、846763６26、4２93９826４261５4、54292４382４、0699467１6713107、８79127326、４1４、5１31４69224、100２3772１671０107、87872８126、4１4、419317324、1203９1６８1671１10７、87771０７26、46４、204１07６９２4、19228９44２061107、84664462６、42７、8５７6930６2４、2803847１1６70８１０7、８７６237７2６、46３、884１７０5324、28７78４９41６417107、877９82626、464、４3８8080４2４、3２９3296７1670９107、８764929２６、4６4、1544752424、45９0881１１6７12107、872760２26、46３、1６1３623124、５35291６11670310７、869３195２６、4６2、4５6256９324、78０４１86６16700１０7、8663１４1２６、4６1、791384９624、9４84０461１6７2９１0７、8612142６、460、7８764５25、32294326１64１5１0７、８8９7９362６、39２3３２362100268、82９605９52５、4372４3331672１107、８8829７７26、392４２43122０26８、47３2６30425、488183061６704107、８8８６８62６、3９１54６524０26８、６4３２554825、5６312１5１167１8107、89０08０126、399、0４６111３825、5９913629１6７1９1０7、88878９2６、３98、736098９72５、６37９9３38１671710７、８８93801２6、３8838１7８2２0２69、0８56３６2９25、8629952４16７28107、859400７26、４6１、１１２776192５、９996312８１6418107、85863226、460、989６805826、０7４7７9641６720１07、89238７９26、382、298２0６６1２6、395２97751６７26１0７、85517１２26、39９2182４２50160、4214256326、3９61１7891６7２７１07、85３194５26、３9９7593425015９、943９1７7２6、453１0371６７２5１0７、889494９２６、３8114897230269、72８358３926、6１０067１71672４1０7、8９2341126、３7９536６323０2７0、４9８２5０4726、67０898９1672210７、8９２8６38２6、３786８1172７0２７0、６833４９58２6、7４1178５１６７2310７、８９3０0４６26、3７77４508220２70、78822１９26、８３41１07８16419１０7、８9３212７26、37６9３5３52152７０、８９76267４26、９1１4３３９166９71０７、84000４５26、392212012５0458、20444328２7、9243６64８166941０7、８24３６0２26、3８８39２8７225155、74816442９、22647915１6６961０7、82４491326、3８6632０１２3０155、９８615929、380０９868166９51０7、8244565２6、3８5７17９７220156、０90283９529、46６４09６６１64０５107、8２574１12６、３８18421123015６、7805523529、７46０６5０71６6９2１0７、82510526、3791６3２３2２0156、９7８636１530、03369０37１6６８91０7、8２370９526、37６55737２60157、03１00４30、360６4281６688１07、8２05115２6、3755671４22５156、５８60486730、64695562１66901０７、8198８６726、3７４４83432３0156、60１５996530、７８55５571１６６9３107、81８9453２６、3７6、7391６78231、088689631669１1０7、8１733４72６、367５21472２０256、9４4２1５６631、58721６9３1668610７、8５5111１26、３6８、501423293５、５716438416687１07、８72１３８926、３1、75８３42673５、6０７７８５6116４0８107、8５6２77826、3８、92288５0２35、８8９４9５471６684107、8570２9226、369、０777105３35、90９4５451668310７、85５58３３26、38、8081471535、９1７２88521668510７、85６2526、368、9６7７５573５、97117274166５１１0７、808８04826、32２５42４328015９、988198８7３６、33９49103１6６44107、8088９0６26、322460912８0160、00８3284836、34２５６85216407107、8084５２82６、32224409２5459、9610０21８36、3８771571１664910７、808194４2６、3259、960２830736、４442１0191662910７、８０8122926、3２1６926６２２0159、９５9３35223６、４590３5４316658１0７、８099１6726、3260、36293907３6、5０68949９1６４1２107、80７888９2６、3212２２２２2３0１５9、965０7３1336、51724171６６4２10７、8095２7８26、320252100１６０、２968994３6、520225４716６3０１07、８07871926、３2１、968２３87436、５24493041663１107、808006126、３２1、９96335０33６、52５71５25１6６4310７、80782９8２6、321、9７2５８07６3６、5３86２96９166５9107、807８31326、３29、987８43436、５５５1４581１6６48107、8０8574726、320、13８18５8９36、5563５3１4１6６34１07、８0７869626、320、00０9938636、5611757116６３21０7、８07756６２６、32９、９８28033536、566152５4１6641107、8082579２6、320、0８46269136、56７４５３116638107、80784４７26、32６0、014871０736、582０5８63162６３1０7、8０762６、32068２５90259、96８７7５8736、585３96861６6２810７、8０7４9３3２６、329、94８1７21536、5８６294916６37107、8076659２6、3２9、9８487２3936、5885７038１６4０9107、807578３26、32９、9698191３6、５9135３82１664０１07、8０７68５326、329、99182１４436、59194１34１６635１07、８07５2452６、329、９610392836、5936027166５4107、8０76667２６、329、９93８04２7３６、598２70081６63910７、807416726、3２9、9４47704436、599535４16６5７107、80７66０8２６、32、9９９5937536、６０5970９1１66４51０7、８076101２6、３2０、０0038911３６、618１０896１6650107、80７578426、3２０、００1２５7６736、6２6109８４16６４710７、807553２26、32、004０9３1536、6348529８1663310７、80743１１2６、319５215523001６0、043８9０４93６、70613８3２1６653107、80741６5２６、31933３27２４０160、05７9８5７2３6、7250532７１6660１０７、８07356３２6、360、1005008７３6、７８５８４3651６64６10７、8０7186６2６、3６0、０7１１24５23６、79083８４116636１０7、8０６６８742６、31857748220１60、0１４040０4３6、83815381641０１07、８０５6９4４26、３５９、8532４74336、879４6961665２107、8０5861１26、31725215160、005062０４37、０１1621７６16656107、８０621０22６、31６９3243２１５260、0８4２694537、02２81434166５5107、80５５278２6、3１６8611122０15９、9888868４３7、06７505７416682１０7、85８583326、283972２2２2０270、５119４37237、92０92２５16７３110７、779138226、3２3４８072１2０155、6０６832１７38、00７４61７７1６７5８１07、820722２26、2988０55621０26３、7０1146623８、0３92099９167５6107、８２0４44426、2９86６6６72１0２63、66982２3３８、066６9７４６1673310７、７797714２6、3２161875１15255、8693５０14３８、138７0７6７１6732107、７7818９８２６、325、659238４６3８、24494853167３0１07、776６69626、322536572102５5、35680３6538、24908６09１6757１０7、82５97２2２6、28880556２202６5、19９4234８3８、789３9２131６76０107、８３030５626、28６３611１2202６６、０１１509683８、83７８4143167４８107、82９944４2６、28480５56２10２66、0６０8２3293９、01190４8416749107、8２752７８2６、２８5３3３3322026５、６6639５4６39、068１３３6616759107、8306351２6、282621922０266、30６97７743９、2026９354１6754１07、８2７5１7726、2832９675２２52６5、800792５43９、27４６8223167５１1０7、８26２2２２2６、28383333220２６５、5７3８629939、２79６０６06１6６68１0７、80６3２1２26、293、02761689３9、33９24０２１164１310７、8061322２6、2９2、088２１14439、46257６22１６7５3１０7、8274722２６、2７５77７78215266、28３77328４0、0３943７9316761107、82６６944２6、27４888８9230266、2276280940、16４515241６750107、825４6９６26、271、2945103４40、６094348110、2编程代码10、2、１层次分析法mａtlab代码m=[157;１/512;1/７１/21］;［d，v］＝ｅiｇ(m）z１＝［１1/2;21］[d,v］=eiｇ(z1)z2=[1１/31/41／7；3１1/２1/4;421１/３；７4３１］;[d,v]=eig（z2)z３=[111／2；1１1/2；221］；［d,v]=eiｇ（z３）10、２、2绘制用户点与配送中心与路图ｍatlab代码clc;ｃｌoseall；clｅaralｌ;X＝10７、97２55４61５162;Y=２６、６2；fｉle='D：\ｔｅsｔ\１、xls’；[datatｅｘｔ］=ｘlsｒeaｄ（file)；y=dａta(：，3）；x=ｄａta（:，2）;ｐlｏt(x，ｙ，’+k＇，X，Y，’p