运筹与管理2018，Vol.27Issue(5)：8-14,7.DOI:10.12005/orms.2018.0105
包含随机客户的选择性旅行商问题建模及求解
Modeling and Solving Selective Traveling Salesman Problem with Stochastic Customers
摘要
Abstract
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 .关键词
旅行商问题/路径优化/随机客户/利润/遗传算法Key words
traveling salesman problem/routing problem/stochastic customers/profit/genetic algorithm分类
信息技术与安全科学引用本文复制引用
张梦颖,秦进,梁樑..包含随机客户的选择性旅行商问题建模及求解[J].运筹与管理,2018,27(5):8-14,7.基金项目
安徽大学博士科研启动经费项目资助(J01003251) （J01003251）
