题目整车物流调度系统摘要本题目为物流调度优化问题，从分布在全国的M个主机厂中，将N个品牌的小汽车调运到全国的多个城市，建立数学模型求出最优解，要求总运费最小。
就本文此问题，可以抽象成求起运地到目的地的最短运输路径问题，再根据订单数来确定此路径上运力货车的数量，以及给出运输成本最低的运单。
对于本题目的三个问题，可以建立两个模型。
模型一，运用“图”的知识，将目的地抽象为图中的顶点，由于顶点在图中的分布呈现一定的聚集性，因此，将图划分为若干区域，求解总运输成本最低，即求向各个区域运输小汽车的运输成本最低，这样就可以表示出总运输成本的表达式。
依据约束条件和总运输成本的表达式就可以确定运输成本最低的表达式，求出最优解，并用所给数据来验证该模型。
模型二，分析整合题中所给大量数据，运用模型中图论的知识，可以将运力信息，起运地信息，目的地信息抽象为三张分区域的图，求解运输成本最低，即求解调运货车和运输小汽车费用最低，起运地内部运输费用最低，目的地内部运输费用最低，根据所给约束条件，给出运输成本最低表达式，并用该模型对实际问题求解。
关键词：整车物流调度图最优化设计启发式算法问题重述随着我国经济突飞猛进的发展，物流成为社会分工中重要的环节。
物流系统的优劣也影响了业务流程的运行效率及其成本。
在物流派送过程中，如何安排货车及其各自的行走路程，使得货车在保证完成运输任务的基础上降低运输成本，是物流优化运输系统的关键。
本题目要求我们建立一套物流运输优化系统，来解决以下三个问题，以提高物流运输效率、优化运营成本：问题一要求我们以某个主机厂为出发点，安排货车完成该厂所有订单任务，求运输成本最低的路径的具体运单方案，同时要求是允许将不同订单用同一货车运输，但是不允许将同一订单拆分用不同货车运输；一个运力货车运单的目的地城市的数不超过3个。
问题二要求我们以所有订单为出发点，将商品小汽车进行分级，运输时优先考虑运输级别高的小汽车，如果货车有剩余车位，则可以顺途运输其他城市的订单；如果起运地货车数量不足，也可以从附近城市调运货车来运输本地订单，在以上条件下给出运单方案，使得运输成本最低。
问题三是在问题二的基础上，要求给出考虑货车级数的运单，附件3中已经给出我们货车的评级分数，所以，只需在考虑运输方案时，根据问题二给出订单求解即可。
问题分析对于问题一，从主机厂派出一辆货车，到任意未送货的订单目的地，如果货车运力满足送货点范围内其他目的地的订单数，则可以实现一辆货车派送若干订单。
此处，为了简化运算，我们将若干目的地按地理位置及集散程度划分为不同的区域，此若干区域即为上述送货点范围。
需要注意是，一辆货车的送货目的地不能超过3个，这就给我们提供了一个约束条件。
对所有货车重复上述安排，直到所有订单运送完毕。
由于运输成本受距离和空载的影响，所以，若使运输成本最小，首先要找出最短路径，我们可对得到的可行性路线进行安排处理，求解一个最小路径问题，然后在保证运力货车走的是最小路径的基础上，合理安排不同城市的订单，从而使运力货车的空载数在比较小的范围内，从而确定出运输成本和距离，空载的表达式，据此可以确定完成订单任务的基础上，运输成本最低的运单方案。
关于问题二，将订单起运地与目的地按照地理位置及集散程度划分为不同的若干区域，以此来优化计算，方便处理数据。
此时要注意的时，关于起运地与目的地，要建立不同的大区。
对于大区之间的距离我们看可以采用加权平均的方法来大致确定。
在保证完成任务的情况下，要求总运输成本最低，即可分解为在各大区运输成本最低，即可理解为在每个城市运输成本最低，即运输某个城市的每一个等级的订单最低。
至此，可以清晰的看出，费用的产生主要有三方面，其一就是某个区域内的汽车调运到中心城市的费用。
其二就是大区域之间运输的费用。
其三就是小汽车到达目的区域中心城市后分配到目的区域各个城市的费用。
总的运输成本最低即使这三方面的加权之和最低。
在运输途中必须求出在各优先级下，各大区域内的最优路线，才能保证完成任务并且运输成本最低。
在货车运送的同时，要优先考虑小汽车的优先级，这就要求对订单要求小汽车的级别进行分类处理。
从而确定大区运送路线，小汽车运送顺序，从而得到运单方案。
至于问题三，在问题二的模型上，在对同级别小汽车进行派送的同时，要求优先考虑评分级别较高的货车。
模型假设问题一（1）小客车的类型没有差异。
（2）在运输过程图中各种费用只受路程距离的影响，不受其他因素影响（3）不同货车之间互不影响（4）每个大区域之间没有关联。
（5）某主机厂向外发货，能够找到一种运货方案，使得全国所有的订单都同时发货。
（6）两个城市之间的距离值采用四舍五入法，精确到个位。
问题二、三（1）运力货车在运货过程中互不影响。
（2）假设大区从其他城市调运汽车完成任务后马上复位，调车时对调出地运输力不受影响。
（3）货车从一个区域发货，空载数较小，不考虑顺土运输其他城市订单的问题。
（4）相距非常近的起运地可以考虑成一个地方，相距很近的目的地也可以考虑为一个地方。
（5）调车费用比较小，计算后直接考虑成是运输费用的一部分。
（6）尽量使同一个起运地的订单同时发出，但是不同起运地其发出时间可以考虑成是时间上独立的。
符号说明Tijx：第i个大区域中第j个城市的第x个订单中所需运的小车数Oij：第i个大区域中第j个城市的订单总数Di：第i个大区中的城市数TCijx：第i个大区域中第j个城市第x个订单中的小车Nm：编号为m的运货车的车位数TCm：编号为m的运货车Sij：第i个区域中第j个城市距起运地的距离Sijj+1：第i个区域中第j个城市与第j+1个城市之间的距离di: 某编号货车上的载车辆YF：小汽车的优先级别Cdl：某个大区域货车运送订单总费用Tijt：实际运往某个城市的小车数Rt:划分大区总数Ot：订单总数Ct：一货车运送一次总费用Cr：过路费（0.4元/公里）Ce：空载运输费（0.2元/公里·车位）Cc：运输小车业务费（0.7元/公里·辆）Cf：耗油费（0.5元/公里）模型建立与求解问题一 约束条件① 货车载货量数不超过货车的车位a ． 若只运一个城市中的一个订单，则Tijx<=Nmb ．若运送一个城市的所有订单，则∑=Oij1x Tijx≤Nm,j<=3c ．若运送两个城市的订单，则∑∑==Dii j Oijx Tijx11≤Nm,j<=3d ．若运送三个城市的订单，则∑∑∑===Rti Dij Oijx Tijx111≤Nm,j<=3② 必须完成任务，即∑∑∑===Rti Dij Oijx Tijx111=Ot③ 一个订单只由一辆车运送，即TCijx ⊆TCm 模型建立由问题分析，我们可以将此问题抽象成具有许多节点的数据最小生成树模型问题每一个行程的第一个送货点是距离主机厂最近的未送货的送货点，对此，抽象成以下数据结构图【2】：找到第一个离O（主机厂位置）点最近的节点后，再找下一个距离此节点最近的节点，直到遍历完所有的节点，流程图如下：运用启发式【3】算法，对各种可能的路线进行综合性分析，比较货车运送单个城市的运输成本，和货车运送多个城市的运输成本，经过比较，可以得出以下结论：一辆货车运送的城市越少，运输成本越低。
同时可以得到货车运送城市数量不用情况下的三种方程： 1. 一辆货车运送一个城市的订单Ct=2(Cf+Cr)Sij+CcTijxSij+Ce(2Nm-Tijx)Sij 2. 一辆货车运送两个城市的订单Ct=(Cf+Cr)(Sij+Sij+1+Sijj+1)+Cc(∑=dijx Tijx1Sij+∑-=+Oijdij x TijxSijj11)+CeNm(Sij+Sijj+1+Sijj+1)-Ce(∑=dijx Tijx1Sij+dijSijj+1)3. 一辆货车运送三个城市的订单Ct=(Cf+Cr)(Sij+Sijj+2Sij+1j+2+sij+2)+(Cr+Ce)(Nm-dij)+CrOij+Oij+1+CeNmSij+2+CcTijx(∑=dijx Sij1+∑-=+Oijdij x Sijj 11+∑+--=++1121Oij Oij dij x j Sijj )通过对附件1中的数据进行处理，可以大致将订单目的地划分为六大区域，由于各大区域之间距离比较大，运输成高，所以运送小汽车的所有可能情况仅在同一区域内考虑，不考虑跨区域运送小汽车的情况，分区情况如下将附件1中的数据代入以上数学模型，得到最优化运输路线，使得运输成本最低。
详细路线及费用见下表问题一最优线路安排问题二约束条件①在同一起运地优先安排运输优先级高的小汽车②所有订单必须运送完成，即∑∑∑===RtiDijOijxTijx111=Ot③货车运载量不得超过货车车位，即Tijx<=Nm模型建立通过对附件2中的订单信息进行详细的分析处理简化，对同一起运地并且同一目的地的订单进行汇总，根据起运地，目的地，在地图上的发布及其聚集性，分别划分出相应的起运地（图2-1）与目的地（图2-2）区域，由附件2我们可以得出具有货车的城市分布图（图2-3）.图2-1如图2-1，将汇总后的订单数据按照起运地相近的原则，将订单起运地分为九大区域，分别为乌鲁木齐区域，北京区域，东北区域，成都区域，广西区域，广东区域，福州区域，安徽区域和海南区域。
其中海南区域为特殊目的地，不在考虑范围之内。
起运地划分区域如下图2-2，我们将订单目的地同样按照相近的原则，划分为11区域，分别为乌鲁木齐区域，呼和浩特区域，银川区域，东北区域，北京区域，安徽区域，重庆区域，昆明区域，广西区域，广东区域和福州区域。
图2-2图2-3如图2-3，根据附件所给数据，我们将全国各地拥有货车的城市在地图上标记出来 ，形成货车分布图，方便调用货车时的查用。
通过对各大区进行分析，对各起运地大区与各目的地大区进行联系匹配，可知：运输成本费用最低=起运地内部运输费用最低+目的地内部运输费用最低+调车费用最低+运送费用最低在考虑运送成本时，需要对货车运送一个城市的订单，与货车运送两个城市的订单的费用总计进行比较，从而选出最优路线。
通过各大区之间的最优路线的匹配，使得各大区之间的内部运输费用最低，运送费用最低，来降低运输成本。
结合问题一中已经求出的三种可能情况下的三种方程，我们可得此问题的解答方程：(1) ∑∑==Rt1t Di1i Tijx)Sij-Ce(2Nm +CcTijxSij +Cr)Sij +2(Cf（2）∑∑==Rt1t Di1i（(Cf+Cr)(Sij+Sij+1+Sijj+1)+Cc(∑=dij x Tijx1Sij+∑-=+Oijdij x TijxSijj11)+CeNm(Sij+Sijj+1+Sijj+1)-Ce(∑=dijx Tijx 1Sij+dijSijj+1)）（3）∑∑==Rt 1t Di1i（(Cf+Cr)(Sij+Sijj+2Sij+1j+2+sij+2)+(Cr+Ce)(Nm-dij)+CrOij+Oij+1+CeNmSij+2+CcTijx(∑=dij x Sij 1+∑-=+Oij dij x Sijj 11+∑+--=++1121Oij Oij dij x j Sijj )(Cf+Cr)(Sij+Sij+1+Sijj+1)+Cc(∑=dij x Tijx 1Sij+∑-=+Oijdij x TijxSijj 11)+CeNm(Sij+Sijj+1+Sijj+1)-Ce(∑=dij x Tijx 1Sij+dijSijj+1)）由上述供述可求出由某起运地大区到目的地大区运送所需的总费用。