管理运筹学_专题3.docVIP

管理运筹学专题三 ——多回路运输问题求解 2011/6/9 目录 一、引言 3 二、具体案例分析 3 三、案例求解 4 3.1、LINGO软件求解 4 3.2、枚举法求解 6 3.3、指派问题解法（匈牙利算法）： 7 3.4、EXCEL求解 8 3.5、图论方法求解： 9 四、约束条件下的配送方案 12 4.1、车辆载重5t 12 4.1.1需求变化后的情况 15 4.2、费用限制下的配送方案 15 4.2.1车载无限制下的配送 17 五、参考文献： 18 六、附录 18 管理运筹学专题三案例 一、引言 运筹学中，对旅行商问题的研究一直很深入，并通过各类方法探求出合理的解决途径。 旅行商问题（Traveling Salesman Problem, TSP）字面上的理解是：有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城市的具有最短路程的环路。 TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。 中国邮递员问题（Chinese Postman Problem CPP）一笔画问题（Drawing by one line）配送路线问题（Route of Distribution）多个旅行商问题（Multiple TSP）多回路运输问题（Vehicle Routing Problem, VRP） 多回路运输问题在物流中的解释是对一系列客户的需求点设计适当的路线，使车辆有序地通过它们，在满足一定的约束条件下，如货物需求量、发送量、交发货时间、车辆载重量限制、行驶里程限制、时间限制等等，达到一定的优化目标，如里程最短、费用最少、时间最短，车队规模最少、车辆利用率高。 VRP问题和TSP问题的区别在于：客户群体的数量大，只有一辆车或一条路径满足不了客户的需求，必须是多辆交通工具以及运输工具的行车顺序两个问题的求解。相对于TSP问题，VRP问题更复杂，求解更困难，但也更接近实际情况。 某配送中心从A地出发（货源充足），将货物配送至B、C、D、E各地用户，再返回A地，各地之间的距离（公里）见下表。试确定最短配送路线。 自 至 A B C D E A 10 7 5 3 B 11 4 6 8 C 7 4 7 8 D 4 5 7 3 E 5 8 8 3 方法提示（以下方法供参考，但不限于这些方法，问题6至问题9必须完成）： 1．枚举法：可产生最优解，但如果配送点很多时（如10个点），此方法不行。 2．动态规划：假设无后效性，可得到一个满意解。由于问题本身实际有后效性，所以不一定能产生最优解。 3．指派问题解法（匈牙利算法）：当出现小范围回路时需对上述路线表做一定的调整，而且调整的方式很多，需讨论。 4．用图论的方法来求解此问题。 5．节约法（一种启发式算法）：可得到满意解，不一定是最优解。 6．当B、C、D、E各处货物需求量分别为6.1吨、13.8吨、6.8吨、12.7吨时，配送车辆最大载货量为5吨，试用不同方法探求配送方案，并进行对比分析。 7．由于客户需求的变化，B、C、D、E各处货物需求量分别为6.8吨、13.8吨、6.1吨、12.7吨时，配送车辆最大载货量为5吨，试用不同方法探求配送方案，并进行对比分析。 8．对问题6，运输费用为1.6元/吨·公里，每次装车、卸车费用各30元，空车（载货量少于0.5吨时按空车计收运费）返程费按0.8元/公里计算，试论证采用多大载货量（载货量有5吨、8吨、10吨、12吨、20吨几种规格）的车辆效果最好？ 9．对问题6，运输费用为1.6元/吨·公里，每次装车、卸车费用各30元，空车（载货量少于0.5吨时按空车计收运费）返程费按0.8元/公里计算，试论证采用多大载货量（载货量允许为任意值）的车辆效果最好？ 三、案例求解 3.1、LINGO软件求解 MODEL: SETS:!初始设置; CITY / 1.. 5/: U;!U(i)为地点编号; LINK( CITY, CITY):DIST, X;!DIST为两地间距离; ENDSETS !数据区; DATA: DIST =999 11 7 4 5 10 999 4 5 8 7 4 999 7 8 5 6 7 999 3 3 8 8 3 999; ENDDATA N = @SIZE( CITY);!模型的大小; MIN = @SUM( LINK: DIST * X);!目标函数为点距之和最小的路径; @FOR( CITY( K): @SUM( CITY( I