4.启发式算法
为了克服精确优化方法的不足，可以运用一些经验法则来降低优化模型的数学精确程度，并通过模仿人的跟踪校正过程来求取运输系统的满意解。启发式算法能同时满足详细描绘和求解问题的需要，较精确式算法更加实用。启发式算法中最具有代表性的就是由Clarke和Wright提出的节约法(saving method)。
下面引用Clarke和Wright的论文中的例子说明节约法思考的基本方法。
设配送中心是P0，m个用户分别是P1，P2，…，Pm；Pi和Pj之间的最短距离是di，j，且di，j已知(i，j=l，2…m)。
如果已知发送车辆的吨位，并且每一辆车都可以满载，则研究的目标转化为使所有参加发送的车辆的总发送距离在满足约束条件的基础上最小。
在考虑配送计划时，首先假定在任何情况下，运输网络中的任意两点都有路径可以连通，并且都有最短路线。如果两点间的运输不畅通(例如由于桥梁、险路或交通故障阻塞了某一通道，或者在一段时间内对通过这一段路线的最高货运量有所限制等)，则可以将这些情况转化为相应的约束条件列入方程组中，然后求解。
目前，根据该方法及其改进方法，西方的计算机软件公司开发了许多成功的车辆优化调度软件，在实际应用中获得了良好的经济效益。中国目前在这个方面的研究和应用也有一定的进步。
现在比较成熟的启发式算法很多，它们的区别主要在于求解过程的收敛速度和收敛程度不同。一般可以把启发式算法分为以下四类：
①构造算法。根据一些规则，每一次将不在线路上的点依次增加到线路中去，直到所有的点都被安排进线路为止。该方法最早提出用来解决旅行商问题，求解速度比较快，也很灵活，但有时找到的解离最优解相差很远。
②两阶段算法。对构造算法进行改进，提出了两阶段算法。第一阶段得到一个可行解，第二阶段则对解进行调整。在保持解是可行的基础上，尽力向最优解接近，每一步都用产生的新可行解取代原来的可行解，使得目标函数值得到改进，一直进行到目标函数值再也得不到改进为止。该方法经常运用交互式优化技术，充分发挥人在求解问题过程中的主观能动性。
③不完全优化算法。精确算法中的决策原则在大规模的问题中导致计算量的指数增长，在不完全优化算法中，用启发式准则代替，可以有效缩小解的收缩空间。
④改进算法。从一个初始解开始，通过对当前的解进行反复的局部扰乱，以求得问题的满意解。
目前，用并行计算机进行的并行算法、基于生物遗传原理的遗传算法、tabusearch(禁忌搜索算法)、神经网络理论等在求解TSP、VRP、PDP问题中也有一定的应用和发展，其中tabusearch(禁忌搜索算法)应用较为广泛。
7.4.3 商用车辆的装载优化
本部分讨论企业物流日常运作中经常碰到的运输车辆装载优化问题，其实也是运筹学中着名问题——背包问题的一类变形问题。
背包问题的一般描述是：一名旅游者携带背包去登山，已知他所能承受的背包重量限制为a公斤，现有n件物品供他选择装入背包，第i种物品的单件重量为ai公斤，其价值ci(可以用其来表示该物品对登山重要性的数量指标反映)是携带物品数量xi的函数ci(xi)(i=1，2，…，n)，问：旅游者应如何选择携带各种物品的件数，使其总价值最大？
这类问题在海运、空运及人造卫星内物品的装载等领域中都有重要应用，通称为最优装载问题。而在企业物流运作中，我们通常需要考虑如何在运力(体积、吨位)受到一定制约的情况下，使所装载的货品能够具有最高的价值，或取得最佳的销售业绩，或获得其他最优的绩效指标等等。可见，背包问题有着广泛的实用背景，是日常生活中经常会遇到的实际问题。
【例7.1】 有一辆最大载货量为12吨的货车，用以装载3种货物，每种货物的单位重量及相应的单位价值如表7‐4所示。问应如何装载可使总价值最大？
上面例子中，我们只考虑了背包重量的限制，即所谓“一维背包问题”。如果还增加背包体积的限制为b，并假设第i种物品每件的体积为vi立方米，问：应如何装背包使得总价值最大？这就是“二维背包问题”(即有两个约束条件的背包问题)。
7.4.4 交通运输大规模微观仿真的概述与案例应用
交通运输仿真是采集交通物流数据的重要技术手段，成为解决物流运输计划与方案指定的另一条途径。
依据仿真模型对交通系统描述的细节程度，交通仿真模型可以划分为宏观交通仿真模型(macroscopic traffic simulation models)、微观仿真模型(microscopic traffic simulation models)、中观仿真模型(mesoscopic traffic simulation models)三种。
宏观交通仿真模型对系统实体、行为及相互作用的描述非常粗糙。例如，用某种集合方式展现交通流，比如交通流量、速度和密度。宏观模型可能根本就不涉及车道变换，它假定交通流已被合理地分配给各车道。
微观交通仿真模型非常细致地描述系统实体和它们间的相互作用。例如，微观水平的车道变换不仅涉及当前车道中本车对前车的跟车定律，而且涉及目标车道的假定前车和后跟车的跟车定律，还有精细的驾驶者决策行为模拟，甚至整个车道变换的操纵过程也能被模拟出来。
微观交通仿真模型特别适合于在计算机上精确再现路网上的实际交通状况，这一特点使得微观交通仿真成为评价和研究交通运输运作状况的有力工具。微观模型基本上由两大部分组成：一部分是路网几何形状的精确描述，包括信号灯、检测器和可变信息标志等交通设施；另外一部分是每辆车动态交通行为的精确模拟，这种模拟要考虑驾驶者的行为并根据车型加以区分。
中观交通仿真模型介于宏观交通仿真模型和微观交通仿真模型之间，它也能够细致地描述大多数系统实体，然而相对于微观模型而言，它对实体运动和相互作用的描述就粗糙得多，例如，对每辆车而言，车道变换被描述成建立在相关车道的实体基础上的瞬时决策事件，而非细致的车辆间相互作用。
宏观模型的重要参数是速度、密度和流量，微观模型的重要参数是每辆车的速度和位置，中观模型则融合了微观模型和宏观模型的某些方面。评价和研究交通运输运作状况，并建立接近于真实世界的实际运营情况，从而得出比较可靠、接近最优解的满意方案，往往要涉及一些细部的研究，宏观交通仿真模型在处理此类问题时会显得很困难。
从近年的发展来看，微观交通仿真模型在交通仿真领域已经占据了主流地位，而且计算机技术的飞速发展使得在微机上已经能够运行微观(中观)仿真模型，并且将可研究的范围拓展到一个城市这种仿真规模。近年来，大规模微观仿真模型逐渐在交通物流的研究和工程领域展示出日益重要的作用。本教材重点讨论用微观交通仿真模型，尤其是能够进行大规模微观仿真研究的工具模型。
阅读材料
长江三角洲地区是我国经济最发达的地区之一。随着改革开放的不断深入，经济发展速度加快，原有的交通运输系统暴露出许多问题，如交通路线少，各种运输方式的能力严重不足，原有的运输基础设施严重老化等等。为此，国家计委和世界银行共同对长江三角洲地区的综合运输进行规划研究，这是我国与世界银行合作的软课题中研究范围最广、投入资金最多的项目之一。在这个规划研究中，采用了先进的运输规划和优化理论，从400多个建设项目中筛选出92个项目，并计划在10年内投入880亿元，用于相关交通基础设施建设。
