An upper bound on the minimal total cost of the transportation problem with varying demands and supplies

被引：19

作者：

Xie, Fanrong ^{[1
,2
]}

Butt, Muhammad Munir ^{[3
]}

Li, Zuoan ^{[1
]}

Zhu, Linzhi ^{[2
]}

机构：

[1] Sichuan Univ Sci & Engn, Sch Sci, Zigong 643000, Peoples R China

[2] Nanchang Univ, Dept Math, Nanchang 330031, Jiangxi, Peoples R China

[3] Chinese Acad Sci, Inst Computat Math & Sci Engn Comp, Beijing 100080, Peoples R China

来源：

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE | 2017年 / 68卷

基金：

中国国家自然科学基金;

关键词：

Genetic algorithms; Transportation problem; Transportation problem with varying demands and supplies; Bounds on the minimal total cost; Upper bound on the minimal total cost; ALGORITHM; SYSTEM;

D O I：

10.1016/j.omega.2016.06.007

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

In general cases, to find the exact upper bound on the minimal total cost of the transportation problem with varying demands and supplies is an NP-hard problem. In literature, there are only two approaches with several shortcomings to solve the problem. In this paper, the problem is formulated as a bi-level programming model, and proven to be solvable in a polynomial time if the sum of the lower bounds for all the supplies is no less than the sum of the upper bounds for all the demands; and a heuristic algorithm named TPVDS-A based on genetic algorithm is developed as an efficient and robust solution method of the model. Computational experiments on benchmark and new randomly generated instances show that the TPVDS-A algorithm outperforms the two existing approaches. (C) 2016 Elsevier Ltd. All rights reserved.

引用

页码：105 / 118

页数：14