Skip to main content
SpringerLink
Log in

A Tabu Search Heuristic Procedure for Solving the Transportation Problem with Exclusionary Side Constraints

  • Published:
Journal of Heuristics Aims and scope Submit manuscript

Abstract

A new heuristic procedure for the transportation problem with exclusionary side constraints is developed and implemented. Tabu search, a meta-heuristic method, is used to guide the search to follow a path selectively to prevent from being trapped at local optimal solutions in order to find a global optimal or near global optimal solution. The simplex method on a graph is employed to lead the search from one solution to an adjacent solution in order to take advantage of the underlying network structure of the problem. In the procedure, net changes in cost and in infeasibility are used to measure the attractiveness of a move, and strategic oscillation is used to implement the intensification and diversification functions. A computational experiment was conducted to test the performance of the heuristic procedure and substantial computational results are reported. These results show that the new heuristic procedure finds very good quality solutions and outperforms an existing heuristic procedure in terms of both solution quality and CPU time.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Bradley, G.G., G. Brown, and G. Graves. (1977). "Design and Implementation of Large Scale PrimalTransshipment Algorithms," Management Science 24(1), 1–35.

    Google Scholar 

  • Cao, B. (1992). "Transportation Problems with Nonlinear Side Constraints: A Branch-and-Bound Approach," Zeitschrift fuer Operations Research 36, 185–197.

    Google Scholar 

  • Cao, B. and G. Uebe. (1995). "Solving Transportation Problems with Nonlinear Side Constraints with Tabu Search," Computers & Operations Research 22(6), 593–603.

    Google Scholar 

  • Chen, H. and R. Saigal. (1977). "A Primal Algorithm for Solving a Capacitated Network Flow Problem with Additional Linear Constraints," Networks 7(1), 59–79.

    Google Scholar 

  • Glover, F. (1989). "Tabu Search: Part I," ORSA Journal on Computing 1(3), 190–206.

    Google Scholar 

  • Glover, F. (1990a). "Tabu Search: Part II," ORSA Journal on Computing 2(1), 4–32.

    Google Scholar 

  • Glover, F. (1990b). "Tabu Search: A Tutorial," Interfaces 20(4), 74–94.

    Google Scholar 

  • Glover, F. (1994). "Tabu Search: Improved Solution Alternatives." In J.R. Birge and K.G. Murty (eds.), Mathematical Programming: State of the Art 1994. Dearborn, MI: University of Michigan Press, pp. 64–92.

    Google Scholar 

  • Glover, F.,D. Karney, D. Klingman, and R. Russel. (1978). "Solving Singly Constrained Transshipment Problems," Transportation Science 12(4), 277–297.

    Google Scholar 

  • Glover, F., D. Klingman, and N.V. Phillips. (1992). Network Models in Optimization and Their Applications in Practice. New York, NY: John Wiley & Sons, Inc.

    Google Scholar 

  • Glover, F., E. Taillard, and D. deWerra. (1993). "A User's Guide to Tabu Search," Annals of Operational Research} 41(1-4)}, 3–

    Google Scholar 

  • Glover, F. and A. Løkketangen. (1994). "Solving Zero-One Mixed Integer Programming Problems Using Tabu Search," Working Paper, Graduate School of Business, University of Colorado, Boulder, Colorado.

  • Glover, F. and M. Laguna. (1997). Tabu Search. Hingham, MA: Kluwer Academic Publishers.

    Google Scholar 

  • Kennington, J.L. and R.V. Helgason. (1980). Algorithms for Network Programming. New York, NY: John Wiley and Sons, Inc.

    Google Scholar 

  • Kennington, J.L. and A. Whisman. (1987). "NETSIDE User's Guide," Technical Report 86-OR-01, Department of Operations Research, SMU, Dallas, TX 75275.

  • Klingman, D. and R. Russel. (1975). "Solving Constrained Transportation Problems," Operations Research 23, 91–106.

    Google Scholar 

  • Løkketangen, A. and F. Glover. (1995). "Tabu Search for Zero-One Mixed Integer Programming with Advanced Level Strategies and Learning,"Working Paper, Graduate School of Business, University of Colorado, Boulder, Colorado.

  • Sun, M. and P.G. McKeown. (1993). "Tabu Search Applied to the General Fixed Charge Problem," Annals of Operations Research 41(-4), 405–420.

    Google Scholar 

  • Sun, M., D. Drinka, and J.E. Aronson. (1995). "Implementation Data Structures for a Tabu Search Heuristic Procedure for Solving the Fixed Charge Transportation Problem," Proceedings of the DSI 1995 National Meeting. vol. 2, pp. 915–917.

    Google Scholar 

  • Sun, M., J.E. Aronson, P.G. McKeown, and D. Drinka. (1998). "A Tabu Search Heuristic Procedure for the Fixed Charge Transportation Problem," European Journal of Operational Research, Forthcoming.

Download references

Author information

Authors and Affiliations

  1. Division of Management and Marketing, College of Business, The University of Texas, San Antonio, TX, 78249-0634

    Minghe Sun

Authors
  1. Minghe Sun
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Sun, M. A Tabu Search Heuristic Procedure for Solving the Transportation Problem with Exclusionary Side Constraints. Journal of Heuristics 3, 305–326 (1998). https://doi.org/10.1023/A:1009630528341

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1009630528341

Search

Navigation