包含随机客户的选择性旅行商问题建模及求解

摘要

针对快递配送过程中客户需求具有不确定性的特征,提出一种新的路径优化问题——包含随机客户的选择性旅行商问题,在该问题中客户每天是否具有配送需求存在一定概率,并且对客户进行配送可获取一定利润.同时考虑以上两种因素,建立该问题的数学模型,目标为在满足行驶距离限制的条件下,找出一条经过部分客户的预优化路径,使得该路径的期望利润最大.其可用于模拟构建最后一公里快递配送的路径问题,提供更具有经济效益的配送路径.随后提出包含精细化局部搜索策略的改进遗传算法,算法根据问题特点构建初始可行解.最后通过多个计算比对结果表明,该算法具有较高的计算效率.%A new routing problem is introduced and named as the selective traveling salesman problem with stochastic customers.The problem is put forward to address how to deal with stochastic customer presence under the environment in which an associated profit is obtained once a customer is visited .It is defined on a complete graph in which profits are associated with the vertices and travel costs are associated with the edges .Each vertex ( customer ) has a probability of requiring a visit .It can be used to model the routing problems existed in the direct-to-customer deliveries in the last mile logistics and provide more economic delivery tours .A mathematical formulation is provided after a detailed description of this problem .The objective is to find a subset of customers to visit and a priori tour through those customers which does not violate the maximum expected travel distance constraint and maximizes the expected profit .This problem is NP hard .To solve this complicated problem , an improved genetic algorithm is designed to find the Pareto -optimal solutions , and experiments were conducted on a series of test problems .The computational results show a good performance of the proposed algorithm .