求解卸装一体化车辆路径问题的改进导向局部搜索算法

An Improved Guided Local Search Algorithm for Vehicle Routing Problem with Simultaneous Delivery and Pickup

针对卸装一体化车辆路径问题,提出一种变惩罚函数的导向局部搜索算法(IGLS)。在传统导向局部搜索算法的基础上加入了新的惩罚效用函数,当传统导向局部搜索算法陷入局部最优时,变换惩罚策略后重新搜索,从而扩展搜索的邻域。通过和传统导向局部搜索算法以及TS_GLS算法在不同算例上的仿真结果比较,验证了所提算法在解决卸装一体化车辆路径问题上的有效性和稳定性。

This Paper proposes a Improved Guided Local Search Algorithm （IGLS） based on variable penalty function to solve vehicle routing problem with simultaneous delivery and pickup. We propose a new penalty utility function to guided local search algorithm, change the penalty strategy and search again to extended search neighborhood when the traditional guided local search algorithm fall into a local optimum. Through comparison on several examples with the traditional guided local search algorithm and TS_GLS algorithm , the simulation results illustrate that IGLS is an effective and stabilize method for Vehicle Routing Problem with Simultaneous Delivery and Pickup.