摘 要：车辆路径问题（vehicle routing problem,VRP）是组合优化问题中的一个典型的NP难题。本文在构造了该问题的数学模型以后，着重阐述了求解VRP问题的模拟退火算法设计思路。通过实例计算表明，采用模拟退火算法，解VRP问题效果明显，能为物流配送企业减少运输费用，提高经济效益。
关键词：车辆路径问题（VRP），模拟退火算法，2－opt，插入法
1、引言
车辆路径问题（Vehicle Routing Problem,VRP）最早是由Dantzig和Ramser于1959年首次提出的，它是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的[1]。由此定义不难看出，旅行商问题（Traveling Saleman Problem,TSP）是VRP的特例，由于Gaery[2]已证明TSP问题是NP难题，因此，VRP也属于NP难题。
求解VRP问题的方法有精确算法和启发式算法。精确算法如分枝定界法、割平面法、线性规划法、动态规划法等。启发式算法有遗传算法、TS（Tabu Search）算法、模拟退火算法等。本文在构造VRP数学模型后，通过模拟退火算法进行求解，力图找到满意解。
2、VRP的数学模型
车辆路径优化问题可以描述为：从配送中心用多辆汽车向多个客户进行送货，每个客户的位置和需求量一定，每辆汽车的载重量已知，要求合理安排汽车路线，使得总费用最小，总费用包括运输费用和车辆的固定成本，并满足以下条件：
每条配送路径上各客户的需求量之和不超过汽车载重量；
每个客户的需求必须满足，且只能由一辆汽车送货。
符号的定义：
：表示客户，，为客户的数目，标号表示配送中心，本文为单配送中心的情形；
：表示配送车辆，;
：表示客户之间的距离，可以转化成为运输费用；
式中：等式（1）为目标函数，使得总费用最小；约束式（2）表示每个客户都被访问到，且仅能被访问一次；约束式（3），（4）为每条巡回路线上的配送限制；约束式（7），（8）为0，1变量说明；约束式（5）为车辆的载重量限制；约束式（6）为消去支路约束条件；约束式（9）表示支路约束量恒为非负值。
3、算法设计
本文设计的求解VRP的方法是，首先是随机产生初始解，然后用模拟退火法优化初始解。
3.1 模拟退火算法
KIRKPATRICK等于1983年首次提出模拟退火算法。该算法用于求解优化问题的出发点是基于物理中固体物质的退火过程，与一般优化问题具有相似性，在对固体物质进行退火处理时，常先将它加温使其粒子可以自由运动，以后随着温度的逐渐下降，粒子逐渐形成低能态晶格，若在凝点附近的温度下降速率足够慢，则固体物质定会形成最低能量的基态。对于组合优化问题也存在类似过程，设一个目标函数及其的一个解为，分别与固体能量和微观状态等价，并以控制参数下模拟其温度下降。对于温度的每一个取值，持续进行“产生新解－判断－接受/拒绝”的迭代过程，用一个随机接受准则（METROPOLIS准则）有限度的接受恶化解[3]，使算法能从局部极值区域中跳出，尽可能找到全局最优解，并保证算法的收敛性。