求解PDPTW的混合分组编码智能算法

张 倩，丁根宏

(河海大学理学院，南京 211100)

随着互联网的普及和信息技术的高速发展，人类进入了以网络为主的信息时代。基于Internet开展的电子商务已经逐渐成为人们进行商务活动的新模式。而物流是电子商务的核心力量，其快速、通畅是电子商务可以正常、顺利进行的一个重要保证［1］。

车辆路径问题(vehicle routing problem，VRP)［2］是物流配送系统中的关键环节，是在1959年由Dantzig和Ramser共同提出的。车辆路径问题是近年来研究的一个热点问题，其中最广泛关注的问题如快递问题中的线路优化问题、信件运输与投递问题等［3］。

PDPTW［4－5］是一类具有广泛实际应用的优化组合问题。PDPTW是指一列车队必须完成的运输需求，装货点和卸货点是组成运输任务的2个需求要素。配送中心的每辆车从车库出发，沿所选的最优化路线为客户服务，以满足客户的运输需求，并最终返回车库。车辆在访问客户点时，必须依次服务所有需求，且满足时间窗、负载的限制，并最终返回车库。要用最大装货量和装载货物类型来限制每辆车，但是由于装货点和卸货点所在的实际位置不同，所以车辆必须在给出的时间窗口范围内访问到每个客户点。在解决PDPTW问题时，为了方便，定义其为整数线性规划问题。由于PDPTW问题比VRP问题多了时间窗限制，所以PDPTW是对VRP的扩展，VRP又是TSP的一种推广，而TSP已被证明是一个NP－hard问题［6］。因此，在解决PDPTW也具有许多类似的实际困难。由于PDPTW可以作为物流中运筹规划问题的模型，在实际生活中的应用越来越多，从而引起国内外学者的广泛关注。……