整车物流调度系统

2013第十届五一数学建模联赛承诺书我们仔细阅读了五一数学建模联赛的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与本队以外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其它公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们愿意承担由此引起的一切后果。我们授权五一数学建模联赛赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。 我们参赛选择的题号为（从A/B/C中选择一项填写）：C我们的参赛报名号为：参赛组别（研究生或本科或专科）：所属学校（请填写完整的全名）参赛队员(打印并签名)：1.2.3.日期：2013年5月2日获奖证书邮寄地址：邮政编码2013第十届五一数学建模联赛编号专用页竞赛评阅编号（由竞赛评委会评阅前进行编号）：评阅记录评阅人评分备注裁剪线裁剪线裁剪线竞赛评阅编号（由竞赛评委会评阅前进行编号）：参赛队伍的参赛号码：（请各参赛队提前填写好）：2013第十届五一数学建模联赛题目整车物流调度系统摘要本文对物流的配送方案进行了分析，在考虑小汽车级数和货车评分级数的条件下，对整车的物流调度系统进行优化。运用了遗传和模拟退火模型。对于问题一，本文要考虑的是成本的最小化问题，一方面要考虑汽车行驶的固定成本，另一方面，还要考虑在运送小汽车时可能会产生空载而造成的可变成本。最后在考虑一个起运点最多运送三个订单点的限制条件下，建立模型，目标函数如下：得出最优化订单路径的总费用为万元对于问题二，在问题一的基础上，添加了小汽车的级数，使得小汽车在运送的时候，有一个优先的问题。当货车上存在空位时，可以顺带其他城市的订单，当起运点货车数量不够时，可以向附近调运货车，所以，选取特殊点，建立优化模型，目标函数如下：当起运点货车足够和不足够时，分别建立模型如下：得出运输成本最低为万。对于第三问，在问题二的基础上，添加上货车的车辆评级分数的高低来决定运送的优先次序，因此，在问题二的基础上，加上关于货车车辆优先级别的数学模型，就可以得到问题三的数学模型，目标函数如下：关键词遗传算法模拟退火优化模型整车物流PAGE17一、问题重述1.1问题背景与条件自改革开放以来，我国国民经济的高速发展，带动了巨大的物质产品的刘延东，也就必然导致了物流量的增加。物流成为社会分工中重要的环节。物流系统的优劣也影响了业务流程的运行效率及其成本。因此，要使得社会分工合理，社会资源的配置合理，要使得经济产业的发展，就必须要发展物流产业。1.2问题重述本题目不考虑小客车类型的差异，在运输过程中产生的主要运输成本包括：运输商品小汽车的业务费为元/(公里·辆)，货车运输途中因部分车位空闲而产生的空载运输成本为元/(公里·车位)，油耗动力成本为元/公里，货车过路费用为元/公里。1、建立数学模型考虑从某个主机厂调度货车来完成运输订单，如何安排货车，可以保证在完成运输任务的基础上运输成本最低。并根据你的结果给出运单方案。2、在优先安排级别高的客车的情况下，如果货车有剩余车位，则可以顺途运输其他城市的订单；如果起运地货车数量不足，可以从附近城市调运货车来运输本地订单。请建立数学模型，考虑如何安排货车，可以保证在完成运输任务的基础上运输成本最低。3、对于货车的级数，分数越高说明运输质量和效率越好。故在安排货车运输方案的时候，首先考虑运输成本最小，其次优先安排车辆评级分数较高的货车，在问题的基础上，进行求解并给出新的运单。二、问题分析2.1对于问题一的分析本题要考虑的是起始点北京到各个订单点的各个城市的货车调度问题，在影响货车的调度的因素，有订单点城市的订单分布，还有起始点的货车数量以及各订单点之间的距离。在问题一里面，假设起始地的货车数量是足够的，那就只要考虑订单数与订单点之间的距离。要使得运输成本达到最低，就要尽量在距离近的城市之间行驶，所以在可以只运送一个城市时，就选择运送到达一个订单点，不能做到的时候，就选择两个相近的城市作为订单点。2.2对于问题二的分析问题二在问题一的基础上，增加考虑了小汽车的级数问题，这就使得在小汽车运输的时候，添加了选择的问题。题目的要求是，优先安排级别高的小汽车，在安排完一个订单点的小汽车后，如果仍有空余车位，可以顺带其他城市的订单；在起运点货车数量不够的情况下，可以向附近城市调运货车，这就存在一个选择的问题。我们首先考虑到运送级别最高的小汽车，然后再考虑加上各个级别的小汽车，加以整合，得出模型。2.3对于问题三的分析在问题二的基础上，加上优先安排车辆评级分数高的货车来运输小汽车，即在第二问的基础上添加关于车辆优先级的数学模型就可以了。要满足此条件，即可先定义优先使用评级分数高的货车来运输，在第二问的模型中加入此定义，即可得到满足问题三的模型并加以求解三、模型假设结合本题的实际，本文提出以下几点假设：1、假设小客车类型无差异；2、假设一辆车就出去一次；3、假设货车到目的地之后不返回；4、假设在汽车行驶途中不出现意外；5、假设不考虑时间因素的影响；6、假设不出现运单不满意而产生的退货现象。四、符号说明为了便于问题的求解，我们给出以下符号说明：，分别表示两个订单点第个订单所需要的小汽车数量货车的编号为编号为的货车可运载小汽车的最大量在订单点之间的空余车位两订单点之间的距离编号为的货车在两订单点之间的运营成本编号为的货车在两订单点之间的总运输费当时，订单点的任务由编号为的货车完成；否则当时，编号为的货车从订单点行驶到；否则各地的城市当时，编号为的货车经过城市；否则第订单点所定的级别的小汽车的数量原运输地与调运地之间的距离货车从调运地到起运地的成本五、模型的建立与求解经过以上的分析和准备，我们将逐步建立以下数学模型，进一步阐述模型的实际建立过程。5.1问题一模型的建立与求解5.1.1模型的建立在考虑该问题的时候，结合实际发现：货车在到达目的地之后，会存在是否返回的问题。但是，有时候为了节约成本，在货车返回时，会附带一定的货物，这样就给返回时是否是空载的界定带来一定的麻烦。所以，在模型的建立过程中，我们就假设货车在把小汽车运到目的地之后，不返回。这样就省去了对返回情况的讨论，使得模型的建立更加简便。为了构造数学模型方便，可以引入图论表述。给定一个有向图,是配送点和订单点，,为有向边集，。根据题目可以知道，货车的耗油成本动力为元/公里，货车的过路费用为元/公里，所以，货车运行的固定成本为。考虑到是否有空车位以及空车位的数量，假如有空车位，那么，对于货车的空载产生的运输成本为，运输小汽车产生的成本为，假如没有空车位，那么，货车运输商品小汽车的业务费为，空车位数量可认为是，即。所以，综上所述，货车在运输方面的支出为：综合考虑以上因素，可以得到编号为的货车，在两订单点之间的运营成本为：对于一个公司来说，不可能仅仅只有一辆货车，所以就要考虑到所有的货车的情况。当时表示编号为的货车从订单点行驶到订单点,否则，所以得到总的运输费用为：题目要求的事在完成运输任务的基础上，使得运输成本最小，所以得到目标函数为：在模型的建立过程中，并不是可以对于任意情况都成立的，所以对模型给出一部分的约束条件：只有在订单点的任务才由编号为的货车完成时，即只有在编号为的货车从订单点行驶到时，，即只有在编号为的货车经过城市时，，即：并且，要求（1）编号为p的货车所运输的小汽车量不大于其最大车位（2）每个订单只能由一辆货车服务综上建立模型如下：目标函数为约束条件为：5.1.2模型的求解鉴于本题对于模型优化的要求，本题采用遗传模拟退火算法优化路径，遗传模拟退火算法是将遗传算法和模拟退火的算法结合在一起的一种优化算法，即将模拟退火算法的局部优化能力和遗传算法的全局性并行有效的结合起来，结合本题，具体算法步骤如下：1、给定起运点北京；2、随机选择一个运单城市，计算北京到该运单城市的运费；3、根据该运单城市，选择一个靠近该运单城市的运单城市，且要满足问题一所给的条件；按模拟退火中的接受概率接受或拒绝，并迭代次选出运单路径，对选出的运单路径计算目标值，找出函数值最小的运单路径和这个函数值，记；4、注意经过的运单城市不超过三个；5、在中计算适应度函数,由适应度函数决定的概率分布，从中随机选取个运单路线，形成；6、按遗传算法的常规方法对进行筛选得到，再变异得到；7、令，对计算，找出使函数最小的运单路线和最小函数值，如果，则令，，，返回第二步。我们首先用软件对附件一的原始数据进行处理，得到距离矩阵和订单汇总。如下表：表1各个城市订单总数的汇总城市蒙城福州龙岩三明兰州南宁订单量1050*5104020距离88419652244183416302483城市贵阳遵义漯河商丘郑州大庆订单量10813101020距离244725678799177611404城市牡丹江常德长沙长春葫芦岛盘锦订单量101020101210距离154317351569988448578城市沈阳包头银川东营济南青岛订单量111040121410距离7046671203430454691城市日照成都达州自贡杭州桐乡订单量1935892210距离74719272378213713251313城市金华宁波衢州订单量1107距离150814791546在地图上，可以对这些城市进行标注，以便于在考虑的时候，可以更加直观的看出由北京到这些城市的距离，也便于观察目的地城市之间的距离，在有多个运送目的地的时候，便于直观的进行选择。图1各目的地城市在地图上的标注然后利用软件求解模型，求得（具体程序见附录Ⅰ），即最优化订单路径的总费用为万元，同时求得货车的送货路径分配方案。分配方案如下所示：在配送过程中，为了节省成本，节约资源，当给一个目的地城市运送后还留有空位的情况下，会出现一辆货车运往多个目的地城市的情况，题目规定一辆货车最多运往三个目的地城市。要尽量使得第二城市，第三城市与第一城市之间的距离较短，这样才可以尽可能多的节约成本，达到资源分配的最合理化。表2从北京出发运往三个目的地订单汇总货车编号第一城市第二城市第三城市空位路线19城市常德长沙金华0所发订单数10101路线22城市杭州衢州福州1所发订单数2710运用软件得到的订单路线中，第二城市都是比较靠近第一城市的，第三城市都是比较靠近第二城市的，这样避免了在较远距离的城市之间浪费时间与资源。这样，得到了运往三个目的地城市的情况，并且保证货车的车位几乎不空。上表对运送网三个目的地城市的情况作了汇总，但是还是会出现只送往两个订单点城市的情况，在这样的情况下，就要对起运地与第二城市间的距离进行筛选，选择距离较短的城市进行运送。运用软件得到的订单路线中，满足第二城市距离起运点距离比较短的要求，并且保证了货车的车位几乎不空。下表对运送往两个目的地城市的情况作分析表3从北京出发运往两个目的地订单汇总货车编号第一城市第二城市空位路线34城市长沙贵阳0所发订单数1010路线46城市成都自贡0所发订单数119路线514城市长春牡丹江0所发订单数1010路线615城市郑州商丘0所发订单数1010路线75城市青岛龙岩0所发订单数105路线88城市成都遵义0所发订单数48在实际情况中，为了方便货车的运输，要避免运往多个城市，因为要节省成本，节约资源，当给一个目的地城市运送后还留有空位的情况下，还是会出现一辆货车运往两个以上城市的情况。在实际的运送中，最佳的情况就是只运往一个目的地城市，这样就完全避免了在两个目的地城市之间的路程浪费，最大化节约了成本，下表对仅仅运往一个城市的情况作了汇总：表4从北京出发运往一个目的地订单汇总路线9路线10路线11路线12路线13路线14城市葫芦岛东营沈阳福州兰州银川货车编号111213161718订单数121212202020路线16路线17路线18路线19路线20路线21城市日照成都南宁大庆济南漯河货车编号242535332734订单数202020201414路线22路线23路线24路线25路线26路线27城市杭州达州蒙城三明盘锦包头货车编号3617102022订单数201010101010路线28路线29路线30路线31路线32城市桐乡宁波福州兰州银川货车编号2831192123订单数10102020205.2问题二模型的建立与求解5.2.1模型的建立假设小汽车的级别是，，记。表示订单点的小汽车级数，表示订单点的小汽车级数，，两订单点之间的距离为；对于起运地需要发出的订单来说，其有种不同级别的小汽车，表示属于第订单点的所定的级别的小汽车数量，并且记表示这个起运地所需发出的级别为的小汽车的数量。因为这问要求先安排货车运输级别高的小汽车，那么可以先考虑运输级别的小汽车，用编号为的货车来运输这些小汽车，可以用来表示最先安排的小汽车，此时先运的小汽车量为,那么用货车为p来运输这批小汽车时，由其所属的订单点为,所需的费用为那么对于所有级别的小汽车来说，首先要安排级别高的小汽车装运，那么可以用来限制级别的优先顺序，即总的运输成本为：那么目标函数为：在模型的建立过程中，并不是可以对于任意情况都成立的，所以对模型给出一部分的约束条件：只有在订单点的任务才由编号为的货车完成时，即只有在编号为的货车从订单点行驶到时，，即只有在编号为的货车经过城市时，，即并且，要求（1）编号为p的货车所运输的小汽车量不大于其最大车位（2）每个订单只能由一辆货车服务（3）一个起运地发出的级别为的小汽车的数量要等于各个订单点所需级别为的小汽车总量当起运地货车数量不足的时候，需要从附近的城市调运货车来运输本地的订单，在调运附近城市的货车时，首先在货车过来的路程中需要一些成本，设货车编号为，此运货地与在附近调运货车城市的距离为，则货车在来起运地的途中所需的费用为：在货车调来后，就需要按照上面的方式来优先运输小汽车得到的目标函数：由于在调运的过程中，当起始点的城市货车数量不足的时候，那么就需要从靠近运单城市的其它地区来调运，这时所需要的约束条件为，即要使起运地需向其它城市调运货车时，必须满足在起运地有：其余条件仍然符合上述的约束条件。综上建立模型如下：目标函数为：约束条件为：当需要调运附近城市货车时目标函数为：约束条件为：5.2.2模型的求解鉴于本题对于模型优化的要求，本题采用遗传模拟退火算法优化路径，遗传模拟退火算法是将遗传算法和模拟退火的算法结合在一起的一种优化算法，即将模拟退火算法的局部优化能力和遗传算法的全局性并行有效的结合起来，结合本题，具体算法步骤如下：1、给定起运点北京；2、运单城市的级数从高到低，随机选择一个运单城市，计算北京到该运单城市的运费，如果起运地货车数量不足，就从附近城市调运货车来运输本地订单；3、根据该运单城市，选择一个靠近该运单城市的运单城市，且要满足问题一所给的条件；按模拟退火中的接受概率接受或拒绝，并迭代次选出运单路径，对选出的运单路径计算目标值，找出函数值最小的运单路径和这个函数值，记；4、注意经过的运单城市不超过三个，货车有剩余车位时可以顺途运输其它城市订单；5、在中计算适应度函数,由适应度函数决定的概率分布，从中随机选取个运单路线，形成；6、按遗传算法的常规方法对进行筛选得到，再变异得到；7、令，对计算，找出使函数最小的运单路线和最小函数值，如果，则令，，，返回第二步。如果货车从一个订单点城市到另一个订单点城市移动的距离最短，即移动后得到最优解，而移动距离假如不是最小的，则以一定概率移动到另一个订单点城市，要考虑订单量和货车车位的问题。货车从主机厂到某一个订单点城市开始，参照本题的问题实例，当移动到一个订单点之后，会优先安排运输级别高的小轿车，在货车上还留有空位的前提下，会顺带第二订单点的任务，仍然按照优先安排级别高的小汽车的原则，在还留有空位的条件下，可以顺带第三订单点的任务，直到货车车位无商品小汽车或者到第三个订单点城市。对上面的过程进行循环，直到订单完成。由于本题目涉及数据太多，为表示的方便，在进行计算与整合之后，在正文给出了部分特殊点，具体数值见附录Ⅱ。图2特殊城市的订单运送情况在对各种运输路线进行比较之后，得出，按照以上路线，可使得运输成本最低为万。5.3.模型三模型的建立与求解5.3.1.模型的建立对于这一问，在运输成本最小的情况下优先安排车辆评级分数较高的货车来运输小汽车，因为这是在第二问的基础上进行求解的，那么就只需要在第二问目标函数的基础上添加关于车辆优先级的数学模型即可。记货车的评级为,用来表示评级为的货车；如果要是先用货车评价最高的来运输的话，那么需用来定义优先使用评级高的货车来运输。可记，而在目标函数中就需要把此定义式放在货车能载最大车位的前面作为限制即可得出此问题的目标函数为：第三问是在第二问的基础上添加一个货车评价及的条件，即只需在第二问的基础上约束货车优先级即可，所以约束条件基本不变在模型的建立过程中，并不是可以对于任意情况都成立的，所以对模型给出一部分的约束条件：只有在订单点的任务才由编号为的货车完成时，即只有在编号为的货车从订单点行驶到时，，即只有在编号为的货车经过城市时，，即并且，要求（1）编号为p的货车所运输的小汽车量不大于其最大车位（2）每个订单只能由一辆货车服务（3）一个起运地发出的级别为的小汽车的数量要等于各个订单点所需级别为的小汽车总量综上建立如下模型：目标函数为:约束条件为5.3.2.模型的求解在本题的优化过程中，由一个初始订单点开始，允许出现劣质的中间解，对当然解的反复的局部进行扰乱，跳出局部最优而在全部内寻得最优解。由于亚启发式算法的特点，所以本题继续沿用模拟退火算法和遗传算法。通过多个个体间的遗传操作，对解进行探索，最终求得问题的近似解。但本题加入了新的货车评价分数的限制。要保证优先使用评分较高的货车在进行运输，用模拟退火和遗传算法形成最优解，运用软件最终得到的路线如下图所示：图3北京，邯郸，天津为起点的运输路线图4成都，郑州，重庆为起点的运输路线在图示中，各个圈代表每个城市，直线上的数字代表货车的编号七、模型评价与改进9.1.模型的优缺点分析9.1.1.模型的优点1、假设是合理并且符合实际的；2、在模型的求解时，应用到多种软件，结果严谨并且使人信服；3、本模型易于使用和推广；4、本模型利用经典的数学计算方法和连贯的思路，使得本模型通俗易懂；5、本模型充分使用条件，当约束条件加强时，只需要在前面模型的基础上进行适当的改动即可，使得模型具有很强的实用性和可移植性；6、本模型充分运用车辆调度系统的遗传算法，模拟退火算法。较大程度上取得最优解；7、在数据的处理问题上，剔除了某些不和本题问题的数据（如特殊目的地）。9.1.2.模型的缺点1、模型是在假设的前提下进行的，所以在现实的实践中不可能完全一致；2、利用数学函数和数学算法求的的值都是近似值，得到的不是最优解；3、对影响因素的推测核定都还比较简单，不能精确的概括出所有影响因素；9.2.模型的改进本文的模型是在多种假设的情况下，采用特殊城市得出的结果，在应用到实际中时，不具有广泛性，在后期对模型的整改中，可以对全国各城市进行分析，得到更加具有广泛应用性的模型。其次，本文对很多条件进行了假设，在一定程度上使得模型具有了理想化，在后期对模型的改进中，可以对在本文中假设掉的条件加以考虑。八、模型的推广本模型在一系列的假设下进行了建立与求解，对一些可能会出现的情况做出了假设，在实际的运用中，将我们的假设加一些到模型的考虑因素中，就可以很好的解决在实际生活中的一些配送情况。将本模型优化之后，可以投入实际的物流配送的实践，也可以投入到一些配送方面的实际问题。九、参考文献[1]姜启源，谢金星，叶俊,数学模型（第三版）[M]，北京：高等教育出版社，2005,12；[2]周品，赵新芬,数学建模与仿真,北京：国防工业出版社,2009,4(355)；[3]刘云忠，宣惠玉,车辆路径问题的模型及算法研究综述[J],管理工程学报,2005,(01)；[4]屈授，汪波，钟石泉,单车场多送货点车辆路径问题的改进遗传算法[J],计算机工程与运用,200,（25）。附录附录对模型的具体求解程序如下：model:!订单起始点为北京，设北京到二十三个城市订单点的距离为M;sets:distance/1..23/:M;endsets!求运输成本最低问题;sets:number/1..23/:A,D,T,Y;trucknumber/1..46/:B,X,Z;endsets!目标函数;min=@sum(number(i):@sum(number(j):@sum(trucknumber(p):(0.9+0.2*T+0.7*(B-T))*A*X)));!约束条件;@for(number(j):T)=@for(trucknumber(p):B)-@for(number(i):D);@for(number(i):D*Y)<=@for(trucknumber(p):B);@sum(number(i):Y)=@sum(trucknumber(p):X);@sum(number(i):D*Y)<=@sum(trucknumber(p):B);!一个订单路线不超过三个订单城市;@sum(trucknumber(p):B)<=3;!定义为整数;@for(number(j):@gin(A));@for(number(i):@gin(D));@for(number(j):@gin(T));!定义为整数;@for(trucknumber:@gin(B));!定义Y为0,1变量;@for(number(i):@bin(Y));!定义X为0,1变量;@for(trucknumber(p):@bin(X));@for(trucknumber(p):@bin(Z));!这里是数据;Data:D=[105051040201081310102010102010121011104012141019358922101107];B=[1020