物流中心的货物配送

全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：湖南文理学院参赛队员(打印并签名)：1.李世林2.苏敏艺3.陈生运指导教师或指导教师组负责人(打印并签名)：日期：2013年08月08日物流中心的货物配送摘要　本文是解决该物流公司的运输配送问题，属于分配组合问题，我们建立了多目标规划模型，采用系统聚类法，借助matlab软件，在各个运输限制因素的影响下，选择最优的运送路线，使得所有运送车辆的总行驶路程最小。针对问题一，首先根据货车最大载重量为Q，客户总需求量为𝑞𝑖，所以至少应为𝑞𝑖/𝑄辆车去运输；然后采用matlab实现多目标规划系统聚类法，并画出聚类树形图，再根据客户的所需物资（也就是货运车数目），将客户分为几类，每一类即是货运车的送货路线；最后由惩罚函数得分对三类路线进行优化，得到送货车辆总运行里程最短的几条路线，即为送货车辆每天总运行里程最短的路线。针对问题二，由问题一，得出送货车辆每天总运行里程最短的三类路线，根据惩罚函数对三类路线进行优化，得到送货车辆总运行里程最短的三条路线：第一条路线：01530；第二条路线：06720；第三条路线：0480；总路程为790km，三辆货运车的载重量都小于货运车的最大载重量，分别为8，8和6吨，这三条路线的惩罚函数在同类路线中最低，分别为3、3.96和0.关键词：matlab软件惩罚函数系统聚类法多目标规划模型1问题的重述某物流中心拥有一支货运车队，每台货运车辆的载重量（吨）相同、平均速度（千米/小时）相同，该物流中心用这样的车为若干个客户配送物资，物流中心与客户以及客户与客户之间的公路里程（千米）为已知。每天，各客户所需物资的重量（吨）均已知，并且每个客户所需物资的重量都小于一台货运车辆的载重量，所有送货车辆都从物流中心出发，最后回到物流中心。物流中心每天的配送方案应当包括：当天出动多少台车？行驶路径如何？由此形成的当天总运行里程是多少？一个合格的配送方案要求送货车辆必须在一定的时间范围内到达客户处，早到达将产生等待损失，迟到达将予以一定的惩罚；而一个好的配送方案还应该给出使配送费用最小或总运行里程最短的车辆调度方案。1.建立送货车辆每天总运行里程最短的一般数学模型，并给出求解方法。2.根据具体的算例进行求解，并给出实际使用的软件名称、命令和编写的全部计算机源程序。2问题分析本文是解决该物流公司的运输配送问题，属于分配组合问题，我们建立了多目标规划模型，在各个运输限制因素的影响下，选择最优的运送路线，使得所有运送车辆的总行驶路程最小。首先根据题目要求分析不难看出，问题二为问题一的实际情况的一般形式，因此，在第一问我们建立送货车辆每天总运行里程最短的一般数学模型，并给出求解方法，第二问在第一问的基础上，代入具体的数据求解。第一步：确定货运车的数目。根据货车最大载重量为Q，客户总需求量为𝑞𝑖（𝑞𝑖𝑄），所以至少应为𝑞𝑖/𝑄辆车去运输。第二步：确定货运车的路线。采用matlab实现上面过程，并画出聚类树形图，再根据客户的所需物资（也就是货运车数目），将客户分为几类，每一类即是货运车的送货路线，此时送货车辆每天总运行里程最短。第三步：建立惩罚函数,,kFCtx。一个合格的配送方案要求送货车辆必须在一定的时间范围内到达客户处，早到达将产生等待损失，迟到达将予以一定的惩罚，所以我们建立惩罚函数F，将损失和惩罚量化，有利于更好的评价路线方案的优越性。3符号说明符号说明𝑄货车最大载重量𝑞𝑖第𝑖个客户总需求量为𝑞𝑖𝐷𝑖𝑗i和j的客户之间的运输距离𝐹惩罚函数,单位时间单位价值的提前与推迟供货的惩罚因子4问题的假设假设一：客户所需物资的重量在货运车出发前已知。假设二：所以货运车同时出发。假设三：每个客户站点仅允许一辆车经过一次并配送货物。假设四：每辆货车之间的运输不受影响，且不受外界因素（如天气）的影响，即货车的平均速度恒定；。假设五：货车行驶路线事先已经确定，即在行驶路上不会额外耗费时间。假设六：每个送货点只有一辆货车运送货物。　　5模型的建立与求解5.1模型的建立5.1.1货运车数目的确定从物流中心开出任一辆货车对物资进行调运，到任意的未配送点。要求每辆车的行驶速度为vkm/h，货车最大载重量为Q，客户总需求量为𝑞𝑖（𝑞𝑖𝑄），所以至少应为𝑞𝑖/𝑄辆车去运输。5.1.2模型的建立令物流中心的编码为0，n个需要配送物资的客户的编码依次为1,2，...，n。设编码为i的客户的所需物资重量为iq（1,2,,in…）吨，m辆送货车辆可以完成所有配送任务，maxq为每辆送货汽车的最大载重量；编码分别为i和j的客户之间的运输距离,0,1,2,,;0,1,2,,ijdinjn……。数学模型的建立还需要定义如下3个主要变量：1）变量,,ijkx。如果车辆k驶过客户i和j之间的道路，,,ijkx取值为1，否则取值为0；2）变量,kiy。如果车辆k为编号为i的客户配送任务，,kiy取值为1，否则取值为0；3）变量,ijd。文中将,ijd定义为客户i和客户j之间的运输距离。建立的数学模型中，目标函数的作用就是使得所有送货汽车的行驶距离之和z最短，即,,,01minminnnmijijkijokzdx同时，建立的约束条件是约束送货汽车的最大载重量，即,max0,1,2,,.nikiiqyqkm…为保证只允许一辆车k完成编号为i的客户的运输任务，即,11,1,2,,.mkikyin…为限制只允许一辆汽车经过某一客户，则有,,,0,,,0,1,2,,;1,2,,,,1,2,,;1,2,,.nijkkiinijkkjjxyjnkmxyinkm…………5.1.3应用系统聚类法求解货物配送系统聚类法的基本思想先将n个样本各自看成一类，然后规定样本之间的距离和类与类之间的距离。开始时各个样本自称一类，类与类之间的距离与样本之间的距离是相等的。选择距离最近的一对合并成一个新类。计算新类和其他类的距离，再将距离最近的两类合并，这样每次减少一类，直至所有的样本都归为一类。最后形成一个亲疏关系图谱（聚类树形图），就可以从图上清晰地看出应分成几类。最短距离法定义类与类之间的距离为两类最近样品间的距离，即𝐷𝑘𝑙=𝑚𝑖𝑛{𝑑𝑖𝑗，𝑥𝑖∈𝐺𝑘，𝑥𝑗∈𝐺𝑙}若某一步类Gk与类Gl聚成一个新类，记为Gm，类Gm与任意已有类Gj之间的距离为𝐷𝑚𝑗=𝑚𝑖𝑛{𝐷𝑘𝑗，𝐷𝑙𝑗}，𝑗≠𝑘，𝑙最短距离法聚类的步骤如下：①将初始的每个样品（或变量）各自作为一类，并规定样品（或变量）之间的距离，我们采用欧氏距离。计算n个样品（或p个变量）的距离矩阵D0，它是一个对称矩阵。②寻找𝐷0中最小元素，设为𝐷𝑘𝑙，将𝐺𝑘和𝐺𝑙聚成一个新类，记为𝐺𝑚，即𝐺𝑚={𝐺𝑘，𝐺𝑙}。③计算新类𝐺𝑚与任一类𝐺𝑗之间的递推公式为：𝐷𝑚𝑗=min𝑥𝑖∈𝐺𝑚,𝑥𝑖∈𝐺𝑗𝑑𝑖𝑗{min𝑥𝑖∈𝐺𝑘,𝑥𝑖∈𝐺𝑗𝑑𝑖𝑗,min𝑥𝑖∈𝐺𝑙,𝑥𝑖∈𝐺𝑗𝑑𝑖𝑗}=min{𝐷𝑘𝑗,𝐷𝑙𝑗}对距离矩阵𝐷0进行修改，将𝐺𝑘和𝐺𝑙所在的行和列合并成一个新行新列，对应𝐺𝑚，新行和新列上的新距离由上式计算，其余行列上的值不变，这样得到的新距离矩阵记为D1.④对𝐷1重复上述对𝐷0的2步操作，得到距离矩阵𝐷2；如此下去，直至所有元素合并成一类为止。我们采用matlab实现上面过程，并画出聚类树形图，再根据客户的所需物资（也就是货运车数目），将客户分为几类，每一类即是货运车的送货路线，此时的路线最短。5.1.4惩罚函数,,kFCtx：如果因为核算方式的不同而算出不同的延误赔偿额，供货商与零售商必将产生争议。为了避免在清算时发生争议，我们大胆假设惩罚函数对与延误时间应该是线性形的，以下我们给出简单的数学证明：考虑某货栈只有一个零售商购买一种货品的情况，假设货栈上限不随时间变化。设惩罚函数可简单表示为,Fxt,x为延误货量，t为延误时间。设客户所需物资的重量上限为C。现只考虑推迟的情况。设某期的定单为货栈上限的两倍，则当期只能发出定单一半的货量，然后设之后连续N期的定单都为货栈的上限，第N+1期无定单，则拖欠的货物只能在第N+1期发出，可认为应赔,FCN。但也可以认为是当期拖欠的货物在第一期发出，而第一期的货物在第二期发出，以次类推，直到第N期的货物在第N+1期发出从而补完拖欠。在这种情况下，其赔偿额为,1NFC。如果,FCN≠,1NFC则零售商会要求按照二者中赔偿额高的那项索取赔偿，而供货商则会认为其调整方式是按二者中赔偿额低的那项实施的，从而双方产生争议。为使不产生争议，必须使,FCN=,1NFC提前的情况可同样证明。所以惩罚函数是延误时间的线性函数，证毕。通常，提前与推迟的惩罚与订单的价值成正比，且与提前、推迟时间成正比，设单位时间单位价值的提前与推迟供货的惩罚因子为,，一般来说,推迟供货会引起信誉度的降低，因此假定。设应交货时间为t，供货时间为't。交货时间为一段时间，例如零售商要求在[1t，2t]这一区间内交货都可。1t为最早交货期，2t为最晚交货期。交货期窗口的提前/推迟供货的惩罚函数可以描述为：这一区间内交货都我们在保证总路程最小的前提下，也要使惩罚函数,,kFCtx取到最小。5.2实例求解5.2.1货运车路线的确定根据问题要求已知客户总需求量为2+1.5+4.5+3+1.5+4+2.5+3=22，而每辆货运车的载重量为Q=8吨，由此可以推算出3辆车比较合理。我们采用matlab计算，画出聚类树形图，如下：由前面推算出3辆车比较合理，所以我们将聚类树形图分为3类，如果要求送货车辆每天总运行里程最短，得出三类路线如下：第一类路线：01530和01530总迟到时间：2.5小时，总路径：S=215千米和总迟到时间：3.8小时，早到时间：0.2小时，总路径：S=215千米,总载重量=8吨≤货运车最大载重量8吨；第二类路线：06720和02760总迟到时间:4.4小时，总路径：S=305千米和总迟到时间：4.1小时，早到时间：3.1小时，总路径：S=305千米，总载重量=8吨≤货运车最大载重量8吨；第三类路线：0480和0840总迟到时间：2.8小时，早到时间：2.2小时，总路径：S=270千米和总路径：S=270千米，总载重量=6吨≤货运车最大载重量8吨；总路程321CCCC=215+305+270=790km5.2.2建立惩罚函数,,kFCtx分析题目可知，此类交货问题属于交货期窗口型，即交货时间为一段时间，例如零售商要求在[1t，2t]这一区间内交货即可。1t为最早交货期，2t为最晚交货期。交货期窗口的提前/推迟供货的惩罚函数可以描述为：2'2'2'11''1),(,0),(],[ttttCtttttttCxtCF一般来说,推迟供货会引起信誉度的降低，因此假定,我们假设=0.4，=0.6，所以交货期窗口的提前/推迟供货的惩罚函