蒋振荣 王花兰 梁院生

摘 要：快递公司送货策略是一种优化设计问题，即在给定送货地点和给定设计规范的条件下，确定所需业务员人数，各业务员的运行线路，总的运行公里数，以及费用最省的策略。该策略主要从最短路经和费用最省两个角度解决该问题， 建立了图模型和动态规划模型并采用启发式算法和动态规划的知识求得最优化结果。根据所建立的两个数学模型，对满足设计要求的送货策略和费用最省策略进行了模拟，在有标尺的坐标系中得到了能够反映运送最佳路线的模拟图。最后，对设计规范的合理性进行了充分和必要的论证。

关键词：快递公司送货；最优化；图模型；多目标动态规划；TSP模型

中图分类号：F618 文献标识码：A

Abstract： Express delivery strategy is an optimization design problem， under that is a given delivery location and design specifications given conditions determines the number of sales needed， to run each line sales， the total number of kilometers run and most of the cost of the policy. The strategy solves the problem by two angles of shortest path and most of the cost. The strategy build a graphical model and dynamic programming model and achieve optimum results by using heuristic algorithms and dynamic programming knowledge. According to two mathematical models established， we simulate express delivery strategy and the most strategy of cost to meet the design requirements and have been able to achieved mimic diagram reflecting the best route in the coordinate system of the scale. Finally， the rationality of the design specifications were adequate and necessary argumentation.

Key words： express delivery； optimization； graph model； multiple objective dynamic programming； TSP model

0 问题重述

在快递公司送货策略中，确定业务员人数和各自的行走路线是本题的关键。这个问题可以描述为：一中心仓库（或配送调度中心）拥有最大负重为25kg的业务员m人，负责对30个客户进行货物分送工作，客户i的快件量为已知，求满足需求的路程最短的人员行驶路径，且使用尽量少的人数，并满足以下条件：

（1）每条送快件的路径上各个客户的需求量之和不超过个人最大负重。

（2）每个客户的需求必须满足，且只能由一个人送货。

（3）每个业务员每天平均工作时间不超过6小时，在每个送货点停留的时间为10分钟，途中速度为25km/h。

（4）为了计算方便，我们将快件一律用重量来衡量，平均每天收到总重量为184.5千克。

出于实际情况的考虑，本研究中对人的最大行程不加限制。……