随着经济全球化和信息化进程的不断加快,物流作为具有广阔前景和增值功能的新兴服务业,正在全球范围内迅速发展,它对于提高国家经济运行质量和效益、优化资源配置、增强企业竞争力和促进企业生产力的发展具有重要意义。运输服务是物流组成中的重要环节,降低运输成本、提高运输质量和效率成为加快物流发展的有效途径。车辆路径问题是运输服务优化中的核心问题,它通过对货物的运输线路进行优化,在满足客户需求的前提下,尽量以最低的运输成本将货物送达目的地。在过去几十年间,车辆路径问题得到了广泛的关注和研究,并取得了丰富的研究成果。本文首先对这类问题的构成、分类以及求解算法的研究现状等进行了归纳和概括。最小-最大车辆路径问题,是与一般车辆路径问题目标不同的一类问题,它要求在整个行车线路中,行程最长的线路行驶距离最短。本文根据这类问题的特点,采用遗传算法和禁忌搜索算法进行了求解。并在禁忌搜索算法中,针对最长的线路生成邻域,将该算法用于标准算例的求解,得到了较好的结果。在实际的线路计划和执行过程中,往往会出现新的客户请求或客户信息的变化,这时要求系统能快速响应这种信息更新,并重新制定线路计划。这类问题称为动态车辆路径问题。对于基本的动态车辆路径问题,本文研究了相应的处理策略,分析了系统的基本组成,将整个动态问题转换为一系列的静态子问题,对子问题采用禁忌搜索算法进行求解。以整个线路的行驶距离作为目标,采用该算法对9个标准算例进行了测试,与文献中其他算法的计算结果相比较,有3个问题得到了最好解,7个问题得到了最好平均解。由于交通管制和客户营业时间等实际约束,某些客户只能在某些时间段接受车辆为其提供的服务,即客户有时间窗限制,本文在带时间窗的动态车辆路径问题中,分析了三种线路间局部搜索方法:重定位法,节点交换法和2-opt*法,以及两种线路内局部搜索方法:2-opt法和Or-opt法,并将这些方法的不同组合应用于静态子问题初始解的改进。通过对标准算例的求解结果进行分析和比较得出:在线路间进行局部搜索时,重定位法的效果最好,2-opt*法次之,节点交换法的最差;在线路内进行局部搜索时,2-opt法优于Or-opt法。同时,也分析了客户出现时间的早晚,客户地理位置的分布以及不同的客户时间窗范围对结果线路中使用的车辆数量,整个线路的行驶距离和客户延迟时间的影响。在带时间窗的动态收取和运送问题中,要求从某一客户的收取点提取货物,送到其相应的运送点。因此要求同一客户的收取点和运送点必须由同一台车辆来执行服务,且必须在访问运送点之前先访问提取点。本文在描述该问题特点的基础上,采用了启发式方法对该问题进行求解,并对基本算例进行了测试。