导　　师： 林良才

学科专业： H1203

授予学位： 硕士

作　　者： ;

机构地区： 华南理工大学

摘　　要： 车辆路径问题是一个重要的物流优化课题，从1959年DANTZIG提出至今，已经有50个年头，其间，出现了大量的变种和求解方法，这些问题和算法都默认一个事实，便是节点(车场或客户)间的权值(时间、费用等)是固定的，然而，这种假设在中国的一些实际情况中，确是不适用。
　　 在中国，75％的干线公路是要收费的，公路的通行费占到整个运输成本的30％-40％，是不可忽略的因素。在中国，公路收费方式有两种，分别是车型收费和计重收费，而计重收费逐渐地代替了车型收费，成为了我国主要的公路收费方式。对于车型收费方式，由于其在车型确定之后，通行费用也便相应的确定下来，因此，节点间的费用也是固定值，对车辆路径问题并无影响，可使用经典的车辆路径问题求解算法去求解。
　　 然而，对于计重收费，由于其是按实际称量的车货总质量和行驶的里程收取通行费，因此，节点之间的费用会随着车辆负载的情况而发生变化，这便与传统的车辆路径问题有着很大的不同。本文便是由这个不同为出发点，研究如何在计重收费下求解车辆路径问题。
　　 由于计重收费下的车辆路径问题问题是一个新的问题，为此，本文首先研究了中国计重收费的各类文献，结合传统车辆路径问题的定义，给出了计重收费下的车辆路径问题的完整描述，并从计重收费这个要素出发，分析该问题的特点，之后，选用了两种现代启发式算法，模拟退火算法和禁忌搜索算法，对计重收费下的车辆路径问题进行求解。
　　 评价一个算法的好坏需要大量的测试数据进行证明，为此本文产生了一些比较接近现实的测试数据，对两种算法进行测试，结果发现，禁忌搜索和模拟退火算法都能很好的提高解的质量，对初始解的改进幅度从40.11％～62.24％之间。只是在算法时间方面，禁忌搜索的时间要远比模拟退火算法的时间要长，特别是对于大规模的测试用例，禁忌搜索需要的时间是模拟退火算法的时间的10倍以上，由此可见，模拟退火算法在这里的表现较禁忌搜索算法要好。

关 键 词： 车辆路径 计重收费 模拟退火算法 禁忌搜索算法 物流优化 干线公路

分 类 号： [F542.6 F252.24]

领　　域： [经济管理] [经济管理]