模拟退火算法在带约束的送货路线优化设计中的应用

摘要

This article is intended to solve the optimal design of delivery routes, given delivery point and the other constraint conditions. Determine the optimal route which use the least time. This paper solves the optimal delivery route problem by transforming it into the traveling salesman problem in graph theory. For question one, it has time restrictions, solving this problem by adding time constraints into a general model to construct a new solution model; for question two, it has no time restrictions, but the total weight and the total volume of goods don't meet the weight and volume restrictions of one person, solving this problem by adding weight and volume restrictions into a general model to construct a new solution model. Then, this article uses the simulated annealing algorithm and group optimization to solve the various problems by programming in Matlab 6.5.%意在解决送货路线优化设计问题，即在给定送货点和其他一些约束的条件下，确定所最优的运行路线，使所用时间最少。通过将设计最优送货路线的问题转换成图论中的旅行商的问题来求解。其中，对于问题一，限定各送货点的送货时间，求解此问题需在一般模型的基础上添加时间约束来构建新的求解模型；而对于问题二来说，其没有时间限制，但其货物的总重量和总体积不满足题目中一次行走的重量和体积的限制，故需在一般模型的基础上添加重量和体积限制来构建新的求解模型。在构建相应模型的基础上，本文结合模拟退火算法以及运用分组优化等思想，通过Matlab 6.5编写程序对问题进行求解。