摘要：具有同时取货和送货需求的双向物流配送路径问题(VRPPD)是经典车辆路径问题的一个重要扩展形式，该问题同时涉及取货和送货问题，针对此类问题，设计一种改进的遗传算法。在交叉过程中，保留不可行染色体，而在变异阶段再对染色体进行可行性调整，既增加了染色体的多样性，加速了寻优过程，又解决了染色体在交叉变异后可能产生不可行染色体的问题，改善了运行结果。仿真试验表明，算法可在较短的时间内得到具有竞争力的解，且具有良好的稳定性，证明了该算法求解VRPPD问题的可行性和有效性。

关键词：车辆路径问题;遗传算法;集货和配送

经典车辆路径问题（VRP）将送货和取货分别考虑，属于单向的物流配送路径问题；而在一次配送中，同时满足客户的取货和送货需求，则属于双向物流配送路径问题，双向物流配送路径问题（vehicle routingproblem with pickups and deliveries, VRPPD）是经典VRP的一个重要扩展形式^[1]。物流领域的这种例子并不少见，如在港口物流区，很多物流企业同时兼有物流中心和货代的功能，集装箱将货物送往物流企业同时需要从物流企业装载货物；还有生活中最常见的送啤酒和饮料的同时要对啤酒瓶、饮料瓶的回收等等。而在现实中将正逆向物流分开单独考虑往往会导致一些不必要的浪费，如在邮政系统中，如果能把取信送信、取包裹和送包裹看成一体、集成操作，不仅能提高服务水平，而且能够降低运营成本；如果配送和取货分开进行，则经济效益将大大下降^[2-4]。研究求解双向物流配送路径问题对于物流、运输企业降低物流成本，提高服务质量，实现物流配送价值，进而提高在市场中的竞争力具有重要意义。