数学优化
计算机科学
路径(计算)
算法
局部搜索(优化)
抓住
概率逻辑
约束(计算机辅助设计)
还原(数学)
随机算法
价值(数学)
线性规划
数学
人工智能
机器学习
程序设计语言
几何学
作者
Ahmed Aly,Adriana Felicia Gabor,Nenad Mladenović,Andrei Sleptchenko
标识
DOI:10.1016/j.cor.2024.106756
摘要
This paper deals with the Delivery Territory Design Problem (DTDP), a districting problem that often occurs in delivery operations. The goal of the problem is to construct clusters of nodes (territories) such that the maximum diameter of a territory is minimized, while the territories designed are balanced w.r.t. some performance measures. We propose to solve the DTDP using a Probabilistic Variable Neighborhood Search (ProbVNS) algorithm based on two local search procedures: a tailored randomized shake procedure that targets both a reduction of infeasibility and diversification, and a deterministic local search based on a linear combination of objective and constraint violation. In addition to searching in different neighborhoods, the ProbVNS also changes the search direction by exploring different penalties for violating constraints. Numerical experiments show that ProbVNS outperforms a recent GRASP with the Path-Relinking (PR) algorithm proposed in the literature in terms of feasibility and objective value. In the tested instances, ProbVNS obtained a lower infeasibility measure in 90% of the instances. For these instances, the average decrease in the objective value was 8.3%, with a maximum decrease of 51%. Finally, the running times of ProbVNS are, on average, 2.7 times lower than those of PR.
科研通智能强力驱动
Strongly Powered by AbleSci AI