基于LINGO的旅行商问题的建模方法

J4 ›› 2014, Vol. 36 ›› Issue (05): 947-950.

基于LINGO的旅行商问题的建模方法

王继强

（山东财经大学数学与数量经济学院，山东济南 250014）

收稿日期:2012-11-12 修回日期:2013-03-05 出版日期:2014-05-25 发布日期:2014-05-25
基金资助:
国家自然科学基金资助项目(10901093)

LINGO-based modeling methods for
the traveling salesman problem

WANG Jiqiang

(School of Mathematics and Quantitative Economics,Shandong University of Finance and Economics,Jinan 250014,China)

Received:2012-11-12 Revised:2013-03-05 Online:2014-05-25 Published:2014-05-25

摘要/Abstract

摘要：

旅行商问题是图论中一类经典的最优化问题，其研究对于其他图优化问题的解决具有重要的理论意义和实际价值。针对旅行商问题建模中的困难之处——如何避免“分割”现象，提供了三种不同的解决方法，并给出了基于当今最流行的优化计算软件LINGO的实证分析。

关键词: 旅行商问题, 模型, 整数规划, LINGO

Abstract:

The traveling salesman problem is a classical optimization problem in graph theory. Its research has important theoretical meaning and practical value for other graphic optimization problems.Aiming at the difficulty in modeling the traveling salesman problemhow to avoid the “separation”phenomenon, three different solutions are proposed. Finally,a case study based on LINGO,the most popular optimization softwares, is given.

Key words: traveling salesman problem;model;integer program;LINGO

王继强. 基于LINGO的旅行商问题的建模方法[J]. J4, 2014, 36(05): 947-950.

WANG Jiqiang. LINGO-based modeling methods for
the traveling salesman problem [J]. J4, 2014, 36(05): 947-950.

[1]	郭昆1，宋杰1，王洁萍2，朱志良1. NoSQL数据库间数据交换代价研究[J]. J4, 20160101, 38(01): 33-40.
[2]	李金熹, 尹首一, 魏少军, 胡杨. 基于MLIR的数据流模型[J]. 计算机工程与科学, 2024, 46(07): 1151-1157.
[3]	温鑫, 曾焘, 李春波, 徐子晨. 面向服务器无感计算的模型推理服务切换方法研究[J]. 计算机工程与科学, 2024, 46(07): 1210-1217.
[4]	田红鹏, 吴璟玮. RIB-NER：基于跨度的中文命名实体识别模型[J]. 计算机工程与科学, 2024, 46(07): 1311-1320.
[5]	张家豪, 邓金易, 尹首一, 魏少军, 胡杨. 基于Actor模型的众核数据流硬件架构探索[J]. 计算机工程与科学, 2024, 46(06): 959-967.
[6]	付晓, 苏醒, 董德尊, 钱程东. 面向众核CPU的稠密线性求解器性能评测与优化[J]. 计算机工程与科学, 2024, 46(06): 984-992.
[7]	佟缘, 姚念民. 基于对span的预判断和多轮分类的实体关系抽取[J]. 计算机工程与科学, 2024, 46(05): 916-928.
[8]	吴瑕, 郑洪英, 肖迪. 一种基于认证文件的双方验证模型水印方案[J]. 计算机工程与科学, 2024, 46(04): 647-656.
[9]	刘子源, 马占有, 李霞, 高滢囡, 何娜娜, 黄瑞祺. 基于模糊测度的模糊分支时态逻辑模型检测[J]. 计算机工程与科学, 2024, 46(04): 676-683.
[10]	申影利, 赵小兵, . 语言模型蒸馏的低资源神经机器翻译方法[J]. 计算机工程与科学, 2024, 46(04): 743-751.
[11]	刘仲, 李程, 田希, 刘胜, 邓让钰, 钱程东. MVSim：面向VLIW多核向量处理器的快速、可扩展和精确的体系结构模拟器[J]. 计算机工程与科学, 2024, 46(02): 191-199.
[12]	钟卓辉, 陈黎飞, . 基于模型的非凸聚类算法[J]. 计算机工程与科学, 2024, 46(02): 292-302.
[13]	孙庆骁, 刘轶, 杨海龙, 王一晴, 贾婕, 栾钟治, 钱德沛. GNNSched：面向GPU的图神经网络推理任务调度框架[J]. 计算机工程与科学, 2024, 46(01): 1-11.
[14]	肖振国, 陈林书, 孙少杰, 梅本霞, 柳媛慧, 赵磊. 基于代数粒的聚类方法[J]. 计算机工程与科学, 2024, 46(01): 150-158.
[15]	范林雨, 李军辉, 孔芳. 基于无监督预训练的跨语言AMR解析[J]. 计算机工程与科学, 2024, 46(01): 170-178.