彭 维

(重庆城市管理职业学院工商管理学院 重庆 401331)

0 引 言

包装配送问题是典型的组合优化问题[1]，通常可以描述为：从一个配送中心出发，安排若干车辆为客户配送包装，要求在满足交货时间、车辆载重、客户需求量等条件下，合理安排配送线路，使配送的路程、时间或者费用达到最优。近年来，随着电子商务深入发展，包装需求量和配送量井喷式增长，包装配送问题愈发受到重视，其求解算法也逐渐成为了学者们的研究热点。

分析大量文献可知，包装配送问题的求解算法可以分为精确算法和启发式算法，其中启发式算法占比高达85%左右。这主要是由于包装配送问题属于NP-hard难题，可行解数量会随着问题规模的增大而发生“组合爆炸”，计算开销也随之呈指数式增长[2-3]。精确算法在求解该类问题时，求解效率低、运行速度慢，往往无法取得令人满意的结果。相比之下，启发式算法具有快速寻优能力，可以在较短时间内求得大规模问题的较好解，因此成为了包装配送问题的主要求解算法。目前，应用于包装配送问题的主要启发式算法包括：遗传算法[4]、萤火虫算法[5]、禁忌搜索算法和其他算法[6]。

虽然已有大量优秀算法，但追求更高效的算法一直都是包装配送及其他组合优化问题的重要研究方向[7]。对此，本文引入一种新型启发式算法—水波算法(WWA)，并将其应用于包装配送问题中。WWA算法由郑宇军教授于2014年首次提出，具有参数较少、实现简单、计算开销小等优势[8]。……