王二研究了一段时间的路线规划算法，简直苦不堪言。当年上大学的时候，王二学运筹学还是不错的。当时人比较聪明，留了个心眼，担心老师们以后收利息，就在学校趁着还没毕业把学到的东西全部还给老师了。现在可好，用上了却看不懂，瞅瞅满篇的数字公式、图表、行列式，头大如斗。

　　说起来，路线优化也不全是算法，还是有一些原则。总结起来（这是别人总结，王二偷来滴，当然了，读书人能叫偷吗，那得叫窃）有以下十大原则。

　　1、根据邻近的站点群安排行车路线。车辆的行车路线，要围绕相互靠近的站点群进行计划，使站点之间的行车距离最短。

　　2、从距仓库最远的站点开始设计路线，分派载货能力可以满足该站点群需要的车辆。然后，从还没有分派车辆的其它站点中找出距仓库次远的站店，分派另一车辆，如此往复，直到所有站点都分派有车辆。

　　3、各条行车路线之间要没有交叉，无交叉肯定无重复路线，运行距离会最短。

　　4、优先使用载货最多的车辆进行运送。理想状况是用一辆足够大的车辆运送所有站点的货物，这样将使总的行车距离或时间最小，其实就是规模效应原理的应用（一次载货越多，最好是满载，平均单件运输费用越低）。

　　5、取货、送货应该混合安排，不应该在完成全部送货任务之后再取货。尽可能在送货过程中安排取货，以减少线路交叉次数（取决于车辆结构、取货数量和货物堆放对车辆装卸的影响程度）。

　　6、对特殊情况采取灵活多样的运送方式。特别是对于遥远而无法归入站点群的站点，可以采用其他配送方式。孤立站点，若为其提供服务，所需的运送时间较长、运送费用较高。如果采用小型车辆单独为其进行服务，可能会更经济。此外，利用外包的运输服务也是一个很好的选择。根据经验法则，自营车辆需要达到80%的满载里程才能比受雇运输更便宜。

　　7、避免时间窗口过短，那样会使行车路线偏离理想模式。若出现这种情况，就应该重新进行时间窗口设置，或重新规划配送路线。

　　8、设计配送路线时，要使车辆的行车路线呈水滴状，保证站点群非常紧凑，各站点群的划分要避免重复。

　　9、难运的安排在日班，好运的安排在夜班。对于大城市而言，晚上配送也是一个不错的选择，白天，那个堵啊……

　　10、杜绝以下不合理的运输，包括空车行驶、对流运输、迂回运输（舍近取远）、重复运输、倒流运输、过远运输、运力选择不当、托运方式选择不当、无效运输等。

　　（1）返程或起程空驶。空车无货载行驶，是不合理运输的最严重形式。在实际运输组织中，有时候必须调运空车，从管理上不能将其看成不合理运输。但是，因调运不当、货源计划不周、不采用运输社会化而形成的空驶，是不合理运输的表现。造成空驶的不合理运输主要有以下几种原因：一是能利用社会化的运输体系而不利用，却依靠自备车送货提货，这往往出现单程重车，单程空驶的不合理运输。二是由于工作失误或计划不周，造成货源不实，车辆空去空回，形成双程空驶。三是由于车辆过分专用，无法搭运回程货，只能单程实车，单程回空周转。

　　（2）重复运输：本来可以直接将货物运到目的地，但是在未达目的地之处，或目的地之外的其它场所将货卸下，再重复装运送达目的地。还有一种形式是：同品种货物在同一地点一面运进，同时又向外运出。

　　（3）迂回运输：有两条以上的同类交通线可以采用时，未能利用最短距离的路线，而绕道运送货物至目的地。

　　（4）对流运输：亦称“相向运输”、“交错运输”，指同一种货物，或彼此间可以互相代用而又不影响管理、技术及效益的货物，在同一线路上或平行线路上作相对方向的运送，而与对方运程的全部或一部分发生重叠交错的运输。

　　（5）倒流运输：货物从销地或中转地向产地或起运地回流的一种运输。

　　（6）过远运输：调运物资舍近求远，近处有资源不调而从远处调，这就造成可采取近程运输而未采取，拉长了货物运距的浪费现象。

　　（7）运力选择不当。未选择各种运输工具优势而不正确地利用运输工具造成的不合理现象，常见有以下若干形式：一是弃水走陆。在同时可以利用水运及陆运时，不利用成本较低的水运或水陆联运，而选择成本较高的铁路运输或汽车运输，使水运优势不能发挥。二是铁路、大型船舶的过近运输。不是铁路及大型船舶的经济运行里程，却利用这些运力进行运输的不合理做法。主要不合理之处在于火车及大型船舶起运及到达目的地的准备、装卸时间长，且机动灵活性不足，在过近距离中利用，发挥不了运速快的优势。相反，由于装卸时间长，反而会延长运输时间。另外，和小型运输设备比较，火车及大型船舶装卸难度大、费用也较高。三是运输工具承载能力选择不当。不根据承运货物数量及重量选择，而盲目决定运输工具，造成过分超载、损坏车辆及货物不满载、浪费运力的现象。尤其是 "大马拉小车"现象发生较多。由于装货量小，单位货物运输成本必然增加。

　　（8）托运方式选择不当。对于货主而言，在可以选择最好托运方式而未选择，造成运力浪费及费用支出加大的一种不合理运输。例如应选择整车未选择，反而采取零担托运，应当直达而选择了中转运输，应当中转运输而选择了直达运输等都属于这一类型的不合理运输。

　　（9）无效运输。装运的物资中有无使用价值的杂质（如煤炭中的矸石、原油中的水分、矿石中的泥土和沙石）含量过多或含量超过规定的标准的运输。

　　仓库除了通过第三方物流向本省及周边省市发货外，在省城里也有一些客户，需要送货上门。因为暂时没有TMS支持，确定配送路线，并使用最少的车辆完成配送任务就是需要一个经常要决策的问题。

　　王二数学水平一般，在互联网上找了很多的配送优化算法，看到满篇的计算公式、表格，一个头两个大，太复杂了。最后觉得扫描法比较简便易用。

　　1、因为水西汽配的客户相对比较固定，所以在地图上标出所有配送地点及仓库的位置。

　　2、用一把直尺，以仓库为圆点，沿顺时针（或逆时针）方向旋转，直到与某配送地点相交。核算如果在某线路上增加该站点，是否会超过车辆的载货能力？如果没有，继续旋转直到与下一个配送地点相交。再次计算累计货运量是否超过车辆的运载能力。如果超过，就剔除最后的那个站点，并确定路线。

　　3、随后，从不包含在上一条路线中的站点开始，继续旋转直尺以寻找新路线。重复该过程直到所有配送地点都被安排到路线中。

　　4、根据道路情况（考虑堵车时点、单行道等因素），排定各路线上每个站点的顺序，使整个路线呈水滴状，以保证行车距离最短。当然，也可以使用旅行商问题模型来求解。

　　路线确定后安排车辆时，要保证各线路配送时点首尾相接。也就是说，如果完成一条路线后开始另一条线路，那么就可以分配同一部车负责第二条路线。因此，将所有运输路线首尾相连按顺序排列，使车辆的空闲时间最短，就可以决定所需车辆数，并使车辆数最少。

　　确定配送路线后，把车辆安排好班次，就决定了给客户的服务水平。对于所谓的最后一公里配送而言，主要是两种常见形式，一般戏称为公交车物流和出租车物流。

　　公交车物流：固定时间发车，要求客户在发车前一定时间内提交订单，仓库接单后备货。一般情况下，汽车配件能做到一天两班。因为线路固定，停靠点也固定，客户收货时间可以预期。这种方式配送成本相对较低，需要的车辆、人员也较少。

　　出租车物流：不管什么时间接到客户订单，马上备货发送。单独送货上门，成本比上一种高得多，需要的车辆、人员也多。一般在客户愿意承担运费的情况下可以采用，不然有可能造成配送的货值（如一条皮带），还不如配送费高的情况。当然，这种情况服务水平最高，批量大、毛利高的产品还是可以采用的。

　　上面提到的旅行商问题，即TSP问题（Traveling Salesman Problem），又称为旅行推销员问题、货郎担问题。其基本思想是：一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市，路径选择的目标是：求得的路径路程为所有路径中的最小值。

　　旅行商问题模型适用于对单一车辆配送路线进行优化，即从某设施出发，访问一定数量顾客后又回到原出发点。

　　解决旅行商问题的算法比较多，最常用的有贪心算法（又称贪婪算法），指在对问题求解时，总是做出在当前看来最好的选择。也就是说，不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解。

　　贪心算法一般都是用计算机进行求解的，计算量比较大，特别是顾客比较多时。下面简单示例算法的思想。如图所示，要求车辆从仓库A出发，送货到B、C、D、E四个客户后再返回仓库A。任意两点间的距离已知（即直线上的数字），试求最佳配送路径。

　　1、选择距出发点最近的客户位置，由于D点距A点最近，故先选择D点；

　　2、从剩下的结点中，选择离当前已选择结点最近的客户，即找出离D点最近的点，这一点是C点；

　　3、如果所有位置都被选择了，则停止；否则继续上一步骤，下一个找到的点是E；

　　4、由于只剩下B点没有被选择，所以B点成为继E点之后的客户，然后返回A。

　　这样，最佳配送路线为A—D—C—E—B—A，总行驶距离=15+12+13+18+19=77。

　　表上作业法是根据供销平衡关系和单位物资调运费用，按一定程序编制不同内容的表，由表确定出可行方案，然后判断这一方案是否最优。若不是最优方案则进行调整，往复循环直到求得最优方案，示例如下。

　　3个同一商品的供应商，每日能提供的数量分别是A1为7个单位，A2为4个单位，A3为9个单位。现在要把这些产品全部运到4个门店，各门店每日销量B1为3个单位，B2为6个单位，B3为5个单位，B4为6个单位。已知从各供应商到各门店的单位产品运价，问题是如何调运产品，在满足各门店需求量的前提下总运费最少。

　　单位运价表

　　供销平衡表

　　一、使用最小元素法，即就近供应，从单位运价表中最小的运价开始确定供销关系，然后次小，一直到给出初始方案为止，步骤如下。

　　1、在单位运价表中找出最小运价为1，这表示先将A2的产品供应给B1。因为供应量大，A2除满足B1的全部需求外，还多余1个单位产品。在供销平衡表的A2、B1交叉格处填上3得表1，并将单位运价表的B1列运价划去得表2。

　　表1

　　表2

　　2、在表2中再找最小运价2，确定A2多余的1个单位供应B3，相应地划去A2行运价，并得到表3、表4。

　　表3

　　表4

　　3、在表4中未划去的元素中再找出最小运价3，这样一步步进行下去，直到单位运价表上的所有元素划去为止。

　　4、最后产销平衡表上得到一个调运方案，见表5，此方案的总运费为86元。

　　表5

　　总结以上步骤：从单位运价表中逐次挑选最小元素，并比较供应量和销量。当供应大于销量时，划去该元素所在列；当供应小于销售时，划去该元素所在行。然后在未划去的元素中再找最小元素，一直循环，直到最终确定供销关系。

　　求出方案之后，要进行最优性检查，常用方法有位势法和闭合回路法。所谓闭合回路法是在表5上每一空格出发找一条闭合回路，它以某空格为起点，用水平线或垂直线向前画，碰到数字格转90度后继续前进，直到回到起始空格为止。

　　判定标准是：从每一空格出发存在和可以找到唯一的闭回路。

　　二、伏格尔法

　　最小元素法的缺点是：可能开始时节省一处的费用，但随后在其他处要多花几倍的运费。伏格尔法考虑到：一供应地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差额。差额越大，说明不能按最小运费调运时，运费增加越多。因而对差额最大处，就应当采用最小运费调运，步骤如下。

　　1、在单位运价表中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行，见表6。

　　表6

　　2、从行或列差额中选出最大者，选择它所在行或列中的最小元素。在表6中B2列是最大差额所在列。B2列中最小元素为4，可确定A3的产品先供应B2的需要，得表7。同时将运价表中的B2列数字划去，如表8。

　　表7

　　表8

　　3、对表8中未划去的元素再分别计算出各行、各列的最小运费和次最小运费的差额，并填入该表中的最右列和最下行，重复第1、2步，直到给出初始解为止，如表9。

　　表9

　　伏格尔法给出的初始解比用最小元素法给出的初始解更接近最优解。

　　将固定量的产品从供应地运往门店，经常会有不同的路线可以选择。如果在路况基本相同的条件下，选择一条最短的路线肯定是既省时间又省钱的，这就是运输中常有的最短路线问题。举例如下：

　　公司要把产品从A地运往B地，根据两地之间交通情况，绘制了网络图。结点代表路线要经过的不同城市，箭头表示两个城市之间的公路，上面标注的数字是每段路的长度。

　　解决方法：

　　1、从终点开始逐步逆向推算，与终点10连接的有两个结点，即9和8。从9和8各只有一条线路到10，都是最短路，分别记为（9—10）100，（8-10）150。

　　2、结点6到终点10的路只有一条需要通过9，记做（6—9—10）300；同样的（5—8—10）400；（7—8—10）275。

　　3、结点2到终点10的路有3条，可以选择经过5或6，而最短路为经过6的线路，记为（2—6—9—10）600，同样（4—6—9—10）500，（3—7—8—10）575。

　　4、最后从A点出发即结点1，要到达B点，必然要经过2、3或4其中一个，显然最短路是经过4的，即（1—4—6—9—10）650。

　　可以通过绘制决策表进行计算。

　　从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径叫做最短路径。Dijkstra算法（迪杰斯特拉算法）应用了贪心算法模式，是目前公认最好的求解最短路径的方法。

　　算法的步骤如下：

　　先生成两个集合，其中遍历过的节点集合为S，集合U中则为其余节点，即未遍历过的节点。

　　1、初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其它顶点，即：U={其余顶点}，若v与U中顶点u有边，则{u,v}正常有权值，若u不是v的出边邻接点，则{u,v}权值为∞。

　　2、从U中选取一个距离v最小的顶点k，把k加入S中（该选定的距离就是v到k的最短路径长度）。

　　3、以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值为顶点k的距离加上边上的权。

　　4、重复步骤2和3，直到所有顶点都包含在S中。

　　举例如下，寻找从A到F的最短路径，其中线上的数字是两地间的距离。

　　A市到E市的公路网如图所示。现有一批货物需要从A市运到E市，图中的节点B1、B2、C1……、代表可以经过的县市站点，箭头表示两点间是连通的；线上的数字表示两点间的运输代价。运输代价可以是时间、距离或时间与距离的加权平均。现在要确定从A市到E市的最佳运输路线，使运输成本最低。

　　首先，根据网络结构特征将整个决策问题划分成4个阶段。决策过程按从终点到起点的逆序进行，因此决策阶段编号是按逆序进行的。

　　其次，按照逆序法对每个阶段的决策问题求解，依次从每个阶段的可选状态中选择一个到终点最短的状态。

　　具体决策过程如下。

　　1、第1阶段的决策：有两个可选状态D1和D2，到终点的距离分别是5和2。

　　2、第2阶段的决策，从C1、C2、C3三个备选状态中选择一个点，使其经过D1到达E的距离最短，决策结果是C1点，到E点的最短距离=8。再从中选择1个点，使其经过D2到达E的距离最短，这时的决策点是C2点，最短距离=7。

　　3、第3阶段的决策：分别从B1、B2、B3中选择一个点，使其经过C1、或C2、或C3到达E点的距离最短。可能的部分最短路径是B2—C1、B2—C2、B2—C3，对应的最短距离分别是14、17、16，即这一阶段的决策点都是B2。

　　4、第4阶段的决策：选择A点，使A经过B1、或B2点到达E的总距离最短，结果是A—B2，距离=5+14=19。

　　每个节点上面的数字（方框中）表示该点到终点E的最短距离，决策的过程可用表1说明。

　　表1

　　最后，按顺序从阶段4到阶段1，就可得到从结点A到结点E的最短路径，A—B2—C1—D1—E，最短距离为（5+6+3+5）=19。

　　应用动态规划法求解运输最短路径问题的基本条件是，必须能将一个具体的路径优化问题转化成多个决策阶段问题，且这种阶段划分必须明确、易识别且满足无后效应。

　　一、经验判断法

　　经验判断法是利用行车人员的经验来选择配送路线的一种主观方法。一般以司机习惯行驶路线和道路行驶规定等为基本标准，拟订出几个不同方案，通过汇总有经验的司机和送货人员的意见，或者直接由配送管理人员凭经验做出判断。这种方法的质量取决于决策者对运输车辆、用户的地理位置和交通线路情况掌握的程度，以及决策者的分析判断能力与经验。尽管缺乏科学性，易受掌握信息详尽程度的限制，但运作方式简单、快速、方便。通常在配送路线的影响因素较多，难以用某种确定的数字关系表达时，或难以用某种单项依据评定时采用。其实大多数情况下，就是因为没有先进的管理工具支持（如TMS），才使用这种凭个人经验的方法。

　　当然，现在通过手机的地图导航（比如百度地图、高德地图），配送人员已经能够实时了解路况，比以前单纯凭经验的时候好了许多。

　　二、综合评价法

　　拟订出多种配送路线方案，并且评价指标明确，只是部分指标难以量化，或对某一项指标有突出的强调与要求，则可以采用加权评分的方式来确定配送路线。步骤如下：拟订配送路线方案、确定评价指标、对方案进行综合评分。

　　举例如下：仓库在选择配送路线方案时确定了10项评价指标，如下表所示。每个评分标准分为4个档次：极差（0分)、差（1分）、较好（2分）、良好（3分）、最优（4分）。同时，根据对各项评价指标的重视程度，确定每项的权值。然后在表上为各配送路线方案评分，根据最后的评分结果在各个方案之间进行比较，确定配送路线。