operations research transportation and assignment problem

Operations Research/Transportation and Assignment Problem

The Transportation and Assignment problems deal with assigning sources and jobs to destinations and machines. We will discuss the transportation problem first.

Suppose a company has m factories where it manufactures its product and n outlets from where the product is sold. Transporting the product from a factory to an outlet costs some money which depends on several factors and varies for each choice of factory and outlet. The total amount of the product a particular factory makes is fixed and so is the total amount a particular outlet can store. The problem is to decide how much of the product should be supplied from each factory to each outlet so that the total cost is minimum.

Let us consider an example.

Suppose an auto company has three plants in cities A, B and C and two major distribution centers in D and E. The capacities of the three plants during the next quarter are 1000, 1500 and 1200 cars. The quarterly demands of the two distribution centers are 2300 and 1400 cars. The transportation costs (which depend on the mileage, transport company etc) between the plants and the distribution centers is as follows:

Which plant should supply how many cars to which outlet so that the total cost is minimum?

The problem can be formulated as a LP model:

The whole model is:

subject to,

The problem can now be solved using the simplex method. A convenient procedure is discussed in the next section.

• Book:Operations Research

Navigation menu

MBA Knowledge Base

Business • Management • Technology

Home » Management Science » Transportation and Assignment Models in Operations Research

Transportation and Assignment Models in Operations Research

Transportation and assignment models are special purpose algorithms of the linear programming. The simplex method of Linear Programming Problems(LPP) proves to be inefficient is certain situations like determining optimum assignment of jobs to persons, supply of materials from several supply points to several destinations and the like. More effective solution models have been evolved and these are called assignment and transportation models.

The transportation model is concerned with selecting the routes between supply and demand points in order to minimize costs of transportation subject to constraints of supply at any supply point and demand at any demand point. Assume a company has 4 manufacturing plants with different capacity levels, and 5 regional distribution centres. 4 x 5 = 20 routes are possible. Given the transportation costs per load of each of 20 routes between the manufacturing (supply) plants and the regional distribution (demand) centres, and supply and demand constraints, how many loads can be transported through different routes so as to minimize transportation costs? The answer to this question is obtained easily through the transportation algorithm.

Uses of Transportation and Assignment Models in Decision Making

Transportation model is used in the following:

• To decide the transportation of new materials from various centres to different manufacturing plants. In the case of multi-plant company this is highly useful.
• To decide the transportation of finished goods from different manufacturing plants to the different distribution centres. For a multi-plant-multi-market company this is useful.
• To decide the transportation of finished goods from different manufacturing plants to the different distribution centres. For a multi-plant-multi-market company this is useful. These two are the uses of transportation model. The objective is minimizing transportation cost.

Assignment model is used in the following:

• To decide the assignment of jobs to persons/machines, the assignment model is used.
• To decide the route a traveling executive has to adopt (dealing with the order inn which he/she has to visit different places).
• To decide the order in which different activities performed on one and the same facility be taken up.

Related posts:

• Operations Research approach of problem solving
• Introduction to Transportation Problem
• Procedure for finding an optimum solution for transportation problem
• Initial basic feasible solution of a transportation problem
• Top 7 Best Ways of Getting MBA Assignment Writing Help
• Introduction to Decision Models
• Transportation Cost Elements
• Modes of Transportation in Logistics
• Factors Affecting Transportation in Logistics
• Export/Import Transportation Systems

One thought on “ Transportation and Assignment Models in Operations Research ”

Leave a reply cancel reply.

Your email address will not be published. Required fields are marked *

Assignment Problem: Meaning, Methods and Variations | Operations Research

After reading this article you will learn about:- 1. Meaning of Assignment Problem 2. Definition of Assignment Problem 3. Mathematical Formulation 4. Hungarian Method 5. Variations.

Meaning of Assignment Problem:

An assignment problem is a particular case of transportation problem where the objective is to assign a number of resources to an equal number of activities so as to minimise total cost or maximize total profit of allocation.

The problem of assignment arises because available resources such as men, machines etc. have varying degrees of efficiency for performing different activities, therefore, cost, profit or loss of performing the different activities is different.

Thus, the problem is “How should the assignments be made so as to optimize the given objective”. Some of the problem where the assignment technique may be useful are assignment of workers to machines, salesman to different sales areas.

Definition of Assignment Problem:

ADVERTISEMENTS:

Suppose there are n jobs to be performed and n persons are available for doing these jobs. Assume that each person can do each job at a term, though with varying degree of efficiency, let c ij be the cost if the i-th person is assigned to the j-th job. The problem is to find an assignment (which job should be assigned to which person one on-one basis) So that the total cost of performing all jobs is minimum, problem of this kind are known as assignment problem.

The assignment problem can be stated in the form of n x n cost matrix C real members as given in the following table:

THE LITERATURE REVIEW FOR ASSIGNMENT AND TRANSPORTATION PROBLEMS.

Operations Research is a logical learning through interdisciplinary collaboration to determine the best usage of restricted assets. In this paper, the importance of Operations research is discussed and the literature of assignment and transportation problem is discussed in detail.

Related Papers

IJIRT Journal

This study discusses the current scenario of Operations Research in the field of Logistics. Five sectors are considered in the study to form a brief understanding of how they use Operations Research techniques and why these techniques are used. Operation research technique help in reducing cost and improve decision making.

Rabindra Mondal

A transportation problem basically deals with the problem, which aims to find the best way to fulfil the demand of n demand points using the capacities of m supply points. Here we studied a new method for solving transportation problems with mixed constraints and described the algorithm to find an optimal more-for-less (MFL) solution. The optimal MFL solution procedure is illustrated with numerical example and also computer programming. Though maximum transportation problems in real life have mixed constraints, these problems are not be solved by using general method. The proposed method builds on the initial solution of the transportation problem which is very simple, easy to understand and apply.

Optimization

Hossein Arsham

The family of network optimization problems includes the following prototype models: assignment, critical path, max flow, shortest path, and transportation. Although it is long known that these problems can be modeled as linear programs (LP), this is generally not done. Due to the relative inefficiency and complexity of the simplex methods (primal, dual, and other variations) for network models, these problems are usually treated by one of over 100 specialized algorithms. This leads to several difficulties. The solution algorithms are not unified and each algorithm uses a different strategy to exploit the special structure of a specific problem. Furthermore, small variations in the problem, such as the introduction of side constraints, destroys the special structure and requires modifying andjor restarting the algorithm. Also, these algorithms obtain solution efficiency at the expense of managerial insight, as the final solutions from these algorithms do not have sufficient information to perform postoptimality analysis.Another approach is to adapt the simplex to network optimization problems through network simplex. This provides unification of the various problems but maintains all the inefficiencies of simplex, as well as, most of the network inflexibility to handle changes such as side constraints. Even ordinary sensitivity analysis (OSA), long available in the tabular simplex, has been only recently transferred to network simplex.This paper provides a single unified algorithm for all five network models. The proposed solution algorithm is a variant of the self-dual simplex with a warm start. This algorithm makes available the full power of LP perturbation analysis (PA) extended to handle optimal degeneracy. In contrast to OSA, the proposed PA provides ranges for which the current optimal strategy remains optimal, for simultaneous dependent or independent changes from the nominal values in costs, arc capacities, or suppliesJdemands. The proposed solution algorithm also facilitates incorporation of network structural changes and side constraints. It has the advantage of being computationally practical, easy for managers to understand and use, and provides useful PA information in all cases. Computer implementation issues are discussed and illustrative numerical examples are provided in the Appendix For teaching purposes you may try: Refined Simplex Algorithm for the Classical Transportation Problem with Application to Parametric Analysis, Mathematical and Computer Modelling, 12(8), 1035-1044, 1989. http://home.ubalt.edu/ntsbarsh/KahnRefine.pdf

Journal of Applied Mathematics and Decision Sciences

In a fast changing global market, a manager is concerned with cost uncertainties of the cost matrix in transportation problems (TP) and assignment problems (AP).A time lag between the development and application of the model could cause cost parameters to assume different values when an optimal assignment is implemented. The manager might wish to determine the responsiveness of the current optimal solution to such uncertainties. A desirable tool is to construct a perturbation set (PS) of cost coeffcients which ensures the stability of an optimal solution under such uncertainties. The widely-used methods of solving the TP and AP are the stepping-stone (SS) method and the Hungarian method, respectively. Both methods fail to provide direct information to construct the needed PS. An added difficulty is that these problems might be highly pivotal degenerate. Therefore, the sensitivity results obtained via the available linear programming (LP) software might be misleading. We propose a unified pivotal solution algorithm for both TP and AP. The algorithm is free of pivotal degeneracy, which may cause cycling, and does not require any extra variables such as slack, surplus, or artificial variables used in dual and primal simplex. The algorithm permits higher-order assignment problems and side-constraints. Computational results comparing the proposed algorithm to the closely-related pivotal solution algorithm, the simplex, via the widely-used pack-age Lindo, are provided. The proposed algorithm has the advantage of being computationally practical, being easy to understand, and providing useful information for managers. The results empower the manager to assess and monitor various types of cost uncertainties encountered in real-life situations. Some illustrative numerical examples are also presented."

IJAR Indexing

Assignment problems deal with the question how to assign n objects to m other objects in an injective fashion in the best possible way. An assignment problem is completely specified by its two components the assignments, which represent the underlying combinatorial structure, and the objective function to be optimized, which models \\\\\\\"the best possible way\\\\\\\". The assignment problem refers to another special class of linear programming problem where the objective is to assign a number of resources to an equal number of activities on a one to one basis so as to minimize total costs of performing the tasks at hand or maximize total profit of allocation. In this paper we introduce a new technique to solve assignment problems namely, Divide Row Minima and Subtract Column Minima .For the validity and comparison study we consider an example and solved by using our technique and the existing Hungarian (HA) and matrix ones assignment method(MOA) and compare optimum result shown graphically.

ام محمد لا للشات

The problem of finding the initial basic feasible solution of the Transportation Problem has long been studied and is well known to the research scholars of the field. So far three general methods for solving transportation methods are available in literature, namely Northwest, Least Cost and Vogel?s Approximation methods. These methods give only initial feasible solution. However here we discuss a new alternative method which gives Initial feasible solution as well as optimal or nearly optimal solution. In this paper we provide an alternate method to find IBFS (Initial Basic Feasible Solution) and compared the alternate method and the existing IBFS methods using a Graphical User Interface. It is also to be noticed that this method requires lesser number of iterations to reach optimality as compared to other known methods for solving the transportation problem and the solution obtained is as good as obtained by Vogel?s Approximation Method (VAM).

Omega-international Journal of Management Science

Krzysztof Kowalski

nikky kumari

A new method called zero point method is proposed for finding an optimal solution for transportation problems with mixed constraints in a single stage. Using the zero point method, we propose a new method for finding an optimal more-for-less solution for transportation problems with mixed constraints. The optimal more-for-less solution procedure is illustrated with numerical examples. Mathematics Subject Classifications: 90C08 , 90C90

Handbooks in Operations Research and Management Science

George Nemhauser

Loading Preview

Sorry, preview is currently unavailable. You can download the paper by clicking the button above.

RELATED PAPERS

Int.J. Contemp.Math.Sciences

Dr. P. Senthil Kumar (PSK), M.Sc., B.Ed., M.Phil., PGDCA., PGDAOR., Ph.D.,

Tomasz Kuszewski

Shashini Nawarathne

Journal of Supply Chain Management System

Publishing India Group

International Journal of Advanced Research in Computer Engineering & Technology (IJARCET)

International Journal of Advanced Research in Computer Engineering & Technology (IJARCET) ijarcet

International Journal of Advance and Innovative Research Volume 6, Issue 1 (XXVII): January - March, 2019

Ishfaq Majeed

Juman Abdeen

Prakash Panangaden

International Journal on Advanced …

Adibah Shuib

Anna Nagurney

Carsten Gottschlich

Operations Research Center …

Ankur Chaudhry

Journal of Heuristics

Mehdi Amini

Discrete Applied Mathematics

Rainer Burkard

David Boyce , Hani Mahmassani , Anna Nagurney

European Scientific Journal ESJ

RELATED TOPICS

•   We're Hiring!
•   Help Center
• Find new research papers in:
• Health Sciences
• Earth Sciences
• Cognitive Science
• Mathematics
• Computer Science
• Academia ©2024

Operations Research, 2nd Edition by

Get full access to Operations Research, 2nd Edition and 60K+ other titles, with a free 10-day trial of O'Reilly.

There are also live events, courses curated by job role, and more.

Assignment Problem

5.1 introduction and formulation.

The assignment problem is a particular case of transportation problem in which the number of jobs (or origins or sources) are equal to the number of facilities (or destinations or machines or persons and so on). The objective is to maximise total profit of allocation or to minimise the total cost. An assignment problem is a completely degenerate form of a transportation problem. The units available at each origin and the units demanded at each destination are all equal to one.

Mathematical Formulation of an Assignment Problem

Given n jobs (or activities) and n persons (or facilities) and effectiveness (in terms of cost, profit, time and others) of each person for each job, the problem lies ...

Get Operations Research, 2nd Edition now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Don’t leave empty-handed

Get Mark Richards’s Software Architecture Patterns ebook to better understand how to design components—and how they should interact.

It’s yours, free.

Check it out now on O’Reilly

Dive in for free with a 10-day trial of the O’Reilly learning platform—then explore all the other resources our members count on to build skills and solve problems every day.

Unbalanced Assignment Problem: Definition, Formulation, and Solution Methods

Table of Contents

Are you familiar with the assignment problem in Operations Research (OR)? This problem deals with assigning tasks to workers in a way that minimizes the total cost or time needed to complete the tasks. But what if the number of tasks and workers is not equal? In this case, we face the Unbalanced Assignment Problem (UAP). This blog will help you understand what the UAP is, how to formulate it, and how to solve it.

What is the Unbalanced Assignment Problem?

The Unbalanced Assignment Problem is an extension of the Assignment Problem in OR, where the number of tasks and workers is not equal. In the UAP, some tasks may remain unassigned, while some workers may not be assigned any task. The objective is still to minimize the total cost or time required to complete the assigned tasks, but the UAP has additional constraints that make it more complex than the traditional assignment problem.

Formulation of the Unbalanced Assignment Problem

To formulate the UAP, we start with a matrix that represents the cost or time required to assign each task to each worker. If the matrix is square, we can use the Hungarian algorithm to solve the problem. But when the matrix is not square, we need to add dummy tasks or workers to balance the matrix. These dummy tasks or workers have zero costs and are used to make the matrix square.

Once we have a square matrix, we can apply the Hungarian algorithm to find the optimal assignment. However, we need to be careful in interpreting the results, as the assignment may include dummy tasks or workers that are not actually assigned to anything.

Solutions for the Unbalanced Assignment Problem

Besides the Hungarian algorithm, there are other methods to solve the UAP, such as the transportation algorithm and the auction algorithm. The transportation algorithm is based on transforming the UAP into a transportation problem, which can be solved with the transportation simplex method. The auction algorithm is an iterative method that simulates a bidding process between the tasks and workers to find the optimal assignment.

In summary, the Unbalanced Assignment Problem is a variant of the traditional Assignment Problem in OR that deals with assigning tasks to workers when the number of tasks and workers is not equal. To solve the UAP, we need to balance the matrix by adding dummy tasks or workers and then apply algorithms such as the Hungarian algorithm, the transportation algorithm, or the auction algorithm. Understanding the UAP can help businesses and organizations optimize their resource allocation and improve their operational efficiency.

How useful was this post?

Click on a star to rate it!

Average rating 1.5 / 5. Vote count: 2

No votes so far! Be the first to rate this post.

We are sorry that this post was not useful for you! 😔

Let us improve this post!

Tell us how we can improve this post?

Operations Research

1 Operations Research-An Overview

• History of O.R.
• Approach, Techniques and Tools
• Phases and Processes of O.R. Study
• Typical Applications of O.R
• Limitations of Operations Research
• Models in Operations Research
• O.R. in real world

2 Linear Programming: Formulation and Graphical Method

• General formulation of Linear Programming Problem
• Optimisation Models
• Basics of Graphic Method
• Important steps to draw graph
• Multiple, Unbounded Solution and Infeasible Problems
• Solving Linear Programming Graphically Using Computer
• Application of Linear Programming in Business and Industry

3 Linear Programming-Simplex Method

• Principle of Simplex Method
• Computational aspect of Simplex Method
• Simplex Method with several Decision Variables
• Two Phase and M-method
• Multiple Solution, Unbounded Solution and Infeasible Problem
• Sensitivity Analysis
• Dual Linear Programming Problem

4 Transportation Problem

• Basic Feasible Solution of a Transportation Problem
• Modified Distribution Method
• Stepping Stone Method
• Unbalanced Transportation Problem
• Degenerate Transportation Problem
• Transhipment Problem
• Maximisation in a Transportation Problem

5 Assignment Problem

• Solution of the Assignment Problem
• Unbalanced Assignment Problem
• Problem with some Infeasible Assignments
• Maximisation in an Assignment Problem
• Crew Assignment Problem

6 Application of Excel Solver to Solve LPP

• Building Excel model for solving LP: An Illustrative Example

7 Goal Programming

• Concepts of goal programming
• Goal programming model formulation
• Graphical method of goal programming
• The simplex method of goal programming
• Using Excel Solver to Solve Goal Programming Models
• Application areas of goal programming

8 Integer Programming

• Some Integer Programming Formulation Techniques
• Binary Representation of General Integer Variables
• Unimodularity
• Cutting Plane Method
• Branch and Bound Method
• Solver Solution

9 Dynamic Programming

• Dynamic Programming Methodology: An Example
• Definitions and Notations
• Dynamic Programming Applications

10 Non-Linear Programming

• Solution of a Non-linear Programming Problem
• Convex and Concave Functions
• Kuhn-Tucker Conditions for Constrained Optimisation
• Quadratic Programming
• Separable Programming
• NLP Models with Solver

11 Introduction to game theory and its Applications

• Important terms in Game Theory
• Saddle points
• Mixed strategies: Games without saddle points
• 2 x n games
• Exploiting an opponent’s mistakes

12 Monte Carlo Simulation

• Reasons for using simulation
• Monte Carlo simulation
• Limitations of simulation
• Steps in the simulation process
• Some practical applications of simulation
• Two typical examples of hand-computed simulation
• Computer simulation

13 Queueing Models

• Characteristics of a queueing model
• Notations and Symbols
• Statistical methods in queueing
• The M/M/I System
• The M/M/C System
• The M/Ek/I System
• Decision problems in queueing

Snapsolve any problem by taking a picture. Try it in the Numerade app?

Introduction to Operations Research

Frederick s. hillier, gerald j. lieberman, the transportation and assignment problems - all with video answers.

Chapter Questions

The Childfair Company has three plants producing child push chairs that are to be shipped to four distribution centers. Plants 1,2 , and 3 produce 12,17 , and 11 shipments per month, respectively. Each distribution center needs to receive 10 shipments per month. The distance from each plant to the respective distributing centers is given to the right: The freight cost for each shipment is $\$ 100$ plus 50 cents per mile. How much should be shipped from each plant to each of the distribution centers to minimize the total shipping cost? (a) Formulate this problem as a transportation problem by constructing the appropriate parameter table. (b) Draw the network representation of this problem. C (c) Obtain an optimal solution.

Tom would like 3 pints of home brew today and an additional 4 pints of home brew tomorrow. Dick is willing to sell a maximum of 5 pints total at a price of $\$ 3.00$ per pint today and $\$ 2.70$ per pint tomorrow. Harry is willing to sell a maximum of 4 pints total at a price of $\$ 2.90$ per pint today and $\$ 2.80$ per pint tomorrow. Tom wishes to know what his purchases should be to minimize his cost while satisfying his thirst requirements. (a) Formulate a linear programming model for this problem, and construct the initial simplex tableau (see Chaps. 3 and 4). (b) Formulate this problem as a transportation problem by constructing the appropriate parameter table. C (c) Obtain an optimal solution.

The Versatech Corporation has decided to produce three new products. Five branch plants now have excess product capacity. The unit manufacturing cost of the first product would be $\$ 31, \$ 29$, $\$ 32, \$ 28$, and $\$ 29$ in Plants $1,2,3,4$, and 5 , respectively. The unit manufacturing cost of the second product would be $\$ 45, \$ 41, \$ 46$, $\$ 42$, and $\$ 43$ in Plants $1,2,3,4$, and 5, respectively. The unit manufacturing cost of the third product would be $\$ 38, \$ 35$, and $\$ 40$ in Plants 1,2 , and 3 , respectively, whereas Plants 4 and 5 do not have the capability for producing this product. Sales forecasts indicate that $600,1,000$, and 800 units of products 1,2 , and 3 , respectively, should be produced per day. Plants $1,2,3,4$, and 5 have the capacity to produce $400,600,400,600$, and 1,000 units daily, respectively, regardless of the product or combination of products involved. Assume that any plant having the capability and capacity to produce them can produce any combination of the products in any quantity. Management wishes to know how to allocate the new products to the plants to minimize total manufacturing cost. (a) Formulate this problem as a transportation problem by constructing the appropriate parameter table. C (b) Obtain an optimal solution.

Suppose that England, France, and Spain produce all the wheat, barley, and oats in the world. The world demand for wheat requires 125 million acres of land devoted to wheat production. Similarly, 60 million acres of land are required for barley and 75 million acres of land for oats. The total amount of land available for these purposes in England, France, and Spain is 70 million acres, 110 million acres, and 80 million acres, respectively. The number of hours of labor needed in England, France, and Spain to produce an acre of wheat is 18,13, and 16, respectively. The number of hours of labor needed in England, France, and Spain to produce an acre of barley is 15,12, and 12, respectively. The number of hours of labor needed in England, France, and Spain to produce an acre of oats is 12,10, and 16, respectively. The labor cost per hour in producing wheat is $\$ 9.00, \$ 7.20$, and $\$ 9.90$ in England, France, and Spain, respectively. The labor cost per hour in pro-ducing barley is $\$ 8.10, \$ 9.00$, and $\$ 8.40$ in England, France, and Spain, respectively. The labor cost per hour in producing oats is $\$ 6.90, \$ 7.50$, and $\$ 6.30$ in England, France, and Spain, respectively. The problem is to allocate land use in each country so as to meet the world food requirement and minimize the total labor cost. (a) Formulate this problem as a transportation problem by constructing the appropriate parameter table. (b) Draw the network representation of this problem. C (c) Obtain an optimal solution.

Reconsider the P \& T Co. problem presented in Sec. 8.1. You now learn that one or more of the shipping costs per truckload given in Table $8.2$ may change slightly before shipments begin. Use the Excel Solver to generate the Sensitivity Report for this problem. Use this report to determine the allowable range to stay optimal for each of the unit costs. What do these allowable ranges tell P \& T management?

The Onenote Co. produces a single product at three plants for four customers. The three plants will produce 60,80 , and 40 units, respectively, during the next time period. The firm has made a commitment to sell 40 units to customer 1,60 units to customer 2 , and at least 20 units to customer 3 . Both customers 3 and 4 also want to buy as many of the remaining units as possible. The net profit associated with shipping a unit from plant $i$ for sale to customer $j$ is given by the following table: Management wishes to know how many units to sell to customers 3 and 4 and how many units to ship from each of the plants to each of the customers to maximize profit. (a) Formulate this problem as a transportation problem where the objective function is to be maximized by constructing the appropriate parameter table that gives unit profits. (b) Now formulate this transportation problem with the usual objective of minimizing total cost by converting the parameter table from part $(a)$ into one that gives unit costs instead of unit profits. (c) Display the formulation in part $(a)$ on an Excel spreadsheet. C (d) Use this information and the Excel Solver to obtain an optimal solution. C. (e) Repeat parts $(c)$ and $(d)$ for the formulation in part $(b)$. Compare the optimal solutions for the two formulations.

The Move-It Company has two plants producing forklift trucks that then are shipped to three distribution centers. The production costs are the same at the two plants, and the cost of shipping for each truck is shown for each combination of plant and distribution center: A total of 60 forklift trucks are produced and shipped per week. Each plant can produce and ship any amount up to a maximum of 50 trucks per week, so there is considerable flexibility on how to divide the total production between the two plants so as to reduce shipping costs. However, each distribution center must receive exactly 20 trucks per week. Management's objective is to determine how many forklift trucks should be produced at each plant, and then what the overall shipping pattern should be to minimize total shipping cost. (a) Formulate this problem as a transportation problem by constructing the appropriate parameter table. (b) Display the transportation problem on an Excel spreadsheet. C (c) Use the Excel Solver to obtain an optimal solution.

Redo Prob. 8.1-7 when any distribution center may receive any quantity between 10 and 30 forklift trucks per week in order to further reduce total shipping cost, provided only that the total shipped to all three distribution centers must still equal 60 trucks per week.

The Build-Em-Fast Company has agreed to supply its best customer with three widgets during each of the next 3 weeks, even though producing them will require some overtime work. The relevant production data are as follows: The cost per unit produced with overtime for each week is 100 more than for regular time. The cost of storage is $\$ 50$ per unit for each week it is stored. There is already an inventory of two wid-gets on hand currently, but the company does not want to retain any widgets in inventory after the 3 weeks. Management wants to know how many units should be produced in each week to minimize the total cost of meeting the delivery schedule. (a) Formulate this problem as a transportation problem by constructing the appropriate parameter table. C (b) Obtain an optimal solution.

The MJK Manufacturing Company must produce two products in sufficient quantity to meet contracted sales in each of the next three months. The two products share the same production facilities, and each unit of both products requires the same amount of production capacity. The available production and storage facilities are changing month by month, so the production capacities, unit production costs, and unit storage costs vary by month. Therefore, it may be worthwhile to overproduce one or both products in some months and store them until needed. For each of the three months, the second column of the following table gives the maximum number of units of the two products combined that can be produced on Regular Time (RT) and on Overtime (O). For each of the two products, the subsequent columns give (1) the number of units needed for the contracted sales, (2) the cost (in thousands of dollars) per unit produced on Regular Time, (3) the cost (in thousands of dollars) per unit produced on Overtime, and (4) the cost (in thousands of dollars) of storing each extra unit that is held over into the next month. In each case, the numbers for the two products are separated by a slash /, with the number for Product 1 on the left and the number for Product 2 on the right. The production manager wants a schedule developed for the number of units of each of the two products to be produced on Regular Time and (if Regular Time production capacity is used up) on Overtime in each of the three months. The objective is to minimize the total of the production and storage costs while meeting the contracted sales for each month. There is no initial inventory, and no final inventory is desired after the three months. (a) Formulate this problem as a transportation problem by constructing the appropriate parameter table. C (b) Obtain an optimal solution.

Transportation Modelling and Operations Research: A Fruitful Connection

Cite this chapter.

• Philippe L. Toint 5  

Part of the book series: NATO ASI Series ((NATO ASI F,volume 166))

655 Accesses

2 Citations

The purpose of this paper is twofold. It first aims at introducing the subject of transportation modelling and therefore at setting the stage for the other contributions of this volume. At the same time, it also aims at pointing out the many connections between transportation modelling and operations research, and the rich and insightful nature of these connections.

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

Access this chapter

Subscribe and save.

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime
• Available as PDF
• Read on any device
• Instant download
• Own it forever
• Compact, lightweight edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info
• Durable hardcover edition

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Unable to display preview.  Download preview PDF.

Similar content being viewed by others

Preface: operations research for transportation

Agent-based models in urban transportation: review, challenges, and opportunities

Computational Intelligence and Optimization for Transportation Big Data: Challenges and Opportunities

R+D in advanced road transport telematics in Europe (DRIVE90). Technical Report DRI-201, DG XIII, EEC, Brussels, March 1990.

Google Scholar  

M. Acutt and J. Dodgson. The impact of economic policy instruments on greenhouse gas emission in australian transport. In D. Henscher, J. King, and T. Oum, editors, Transport Policy , volume 3 of the Proceedings of the 7th World Conference on Transport Research , pages 321–334, Kidlington, UK, 1996. Pergamon.

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network flows , Theory , Algorithms , and Applications . Prentice-Hall, Englewood Cliffs, New Jersey, USA, 1993.

P. Stopher amd M. Lee-Gosselin. Understanding travel behaviour in an era of change . Pergamon, Kidlington, UK, 1996.

M. J. Beckman, C B McGuire, and C. B. Winston. Studies in the economics of transportation . Yale University Press, New Haven (USA ), 1956.

M. E. Ben-Akiva, A. de Palma, and I. Kaysi. Dynamic network models and driver information systems. Transportation Research A, 25 (5): 251–266, 1992.

M. E. Ben-Akiva and S. R. Lerman. Discrete Choice Analysis: Theory and Application to Travel Demand . MIT Press, Cambridge, USA, 1985.

L. Bianco and P. Toth, editors. Advanced Methods in Transportation Analysis . Springer-Verlag, Heidelberg, Berlin, New York, 1996.

M. Bierlaire. Evaluation de la demande en trafic: quelques méthodes de distribution. Anna les de la Société Scientifique de Bruxelles , 105 (1–2): 17–66, 1991.

MATH   Google Scholar  

M. Bierlaire. A robust algorithm for the simultaneous estimation of hierarchical logit models. GRT Report 95/3, Department of Mathematics, FUNDP, Namur, Belgium, 1995.

M. Bierlaire, T. Lotan, and Ph. L. Toint. On the overspecification of multinomial and nested logit models due to alternative specific constants. Transportation Science , (to appear), 1997.

M. Bierlaire and Ph. L. Toint. MEUSE: an origin-destination estimator that exploits structure. Transportation Research B , 29 (1): 47–60, 1995.

Article   Google Scholar  

D. Braess. Uber ein Paradoxon der Verkehrsplanung. Unternehmensforschung , 12: 256–268, 1968.

MathSciNet   Google Scholar  

D. Burton and Ph. L. Toint. On an instance of the inverse shortest path problem. Mathematical Programming , Series A, 53 (1): 45–62, 1992.

Article   MathSciNet   MATH   Google Scholar  

D. Burton and Ph. L. Toint. On the use of an inverse shortest paths algorithm for recovering linearly correlated costs. Mathematical Programming, Series A , 63 (1): 1–22, 1994.

MathSciNet   MATH   Google Scholar  

E. Cascetta. Estimation of trip matrices from traffic counts and survey data: a generalised least squares approach estimator. Transportation Research B , 18 (4/5): 289–299, 1984.

L. Clement, D. Peyrton, and M. Frenois. Review of existing land-use transport models. Technical Report 58, CERTU, Lyon, France, 1996.

M. Cremer and H. Keller. A new class of dynamic methods for the identification of origin-destination flows. Transportation Research B , 21 (2): 117–132, 1987.

S. Dafermos. Traffic equilibrium and variational inequalities. Transportation Science , 14: 42–54, 1980.

Article   MathSciNet   Google Scholar  

S. Dafermos. The general multimodal network equilibrium problem with elastic demand. Networks , 12: 57–72, 1982.

S. Dafermos and A. Nagurney. On some traffic equilibrium theory paradoxes. Transportation Research B , 18: 101–110, 1984.

A. de Palma, P. Hansen, and M. Labbé. Commuters’ paths with penalties for early or late arrival. Transportation Science , 24 (4), 1990.

R. B. Dial. A probabilistic multipath traffic assignment algorithm which obviates path enumeration. Transportation Research , 5 (2): 83–111, 1971.

R. M. Downs and D. Stea. Maps in minds . Harper and Row, New York, 1977.

Y. Ermoliev and R. J.-B. Wets, editors. Numerical Techniques for Stochastic Programming . Springer-Verlag, Heidelberg, Berlin, New York, 1988.

M. Florian, editor. Traffic equilibrium methods . Springer-Verlag, New York, 1976. Lecture Notes in Economics and Mathematical Systems 118.

M. Florian. Mathematical programming applications in national, regional and urban planning. In M. Iri and K. Tanabe, editors, Mathematical Programming: recent developments and applications , pages 57–82, Dordrecht, NL, 1989. Kluwer Academic Publishers.

R. L. Francis, L. F. McGinnis, and J. A. White. Facility Layout and Location . Prentice-Hall, Englewood Cliffs, New Jersey, USA, 1992.

M. Frank. The Braess paradox. Mathematical Programming , 20: 283–302, 1981.

N. H. Gartner. Optimal traffic assignment with elastic demands: a review. Transportation Science , 14: 192–208, 1980.

M. Germain, Ph. Toint, and H. T alkens. International negotiations on acid rains in Northern Europe: a discrete time iterative process. In A. Xepapadeas, editor, Economic policy for the environment and natural resources: techniques for the management and control of pollution , pages 217–236, London, 1996. Edward Elgar Publishing.

M. Germain, Ph. Toint, and H. Tulkens. Financial transfer to ensure cooperative international optimality in stock pollutant abatement. Technical Report 97/4, Department of Mathematics, FUNDP, Namur, Belgium, 1997.

R. G. Golledge and R. J. Stimson. Analytical Behavioural Geography . Croom Helm, New York, 1987.

J. D. Griffiths, editor. Mathematics in Transport Planning and Control . Clarendon Press, Oxford, UK, 1992.

A. Hallefjord, K. JOrnsten, and S. Storoy. Traffic equilibrium paradoxes when travel demand is elastic. Working paper, University of Bergen, Bergen, Norway, 1990.

R. Hammerslag. Dynamic assignment in the three dimensional timespace: mathematical specification and algorithm. US-Italy Joint Seminar on Urban Traffic Networks, June 1989.

D. Hensher, J. King, and T. Oum, editors. Travel Behaviour . Pergamon, Kidlington, UK, 1996. volume 1 of the Proceedings of the 7th World Congress on Transport Research.

P. Jones, editor. Developments in Dynamic and Activity-Based Approaches to Travel Analysis , Aldershot, UK, 1990. Avebury.

H. Julien and O. Morellet. What kind of relationship between model choice and forecast traffic for long distance trips? 5th International Conference on Travel Behaviour, Aix-en-Provence, 1987.

P. Kall and S. W. Wallace. Stochastic Programming . J. Wiley and Sons, Chichester, England, 1994.

H. Keller and G. Ploss. Real-time identification of O-D network flows from counts for urban traffic control. In N. H. Gartner and N. H. M. Wilson, editors, Transportation and traffic theory , pages 267–284, New-York, 1987. Elsevier. Proceedings of the Tenth International Symposium on Transportation and Traffic Theory, July 8–10 1987, MIT, Cambridge, Massachusetts.

A. Khasnabis and B. Chaudry. Transportation-land us interaction: the US experience and future outlook. In D. Henscher, J. King, and T. Oum, editors, Transport Policy , volume 3 of the Proceedings of the 7th World Conference on Transport Research , pages 21–30, Kidlington, UK, 1996. Pergamon.

F. Leurent. Cost versus time equilibrium over a network. Transportation Research Record , 1443: 84–91, 1994.

F. Leurent. Pour certifier un modèle . PhD thesis, Ecole National des Ponts et Chausées, Paris, 1996.

M. J. Lighthill and G. B. Whitnam. On kinematic waves ii: a theory of traffic flow on long crowded roads. Proceedings of the Royal Society , London , 229A, 1955.

R. H. Logie and M. Denis. Mental Images in Human Cognition . North-Holland, Amsterdam, 1991.

R. F. Love, J. G. Morris, and G. O. Wesolowsky. Facilities location. Models e.4 methods . Elsevier ( North Holland ), New York, 1988.

J. L. Madre and J. Maffre. Toujours plus loin...mais en voiture. INSEE Première , 417, 1995.

A. M. MacEachren. Travel Time as the Basis of Cognitive Distance. The Professional Geographer , 32 (1): 30–36, 1980.

A. M. MacEachren. How Maps Work: Representation , Vizualization and Design . Guilford Press, New York, 1995.

McNally and Recker. Activity-Based Models of Travel Behaviour: Evolution and Implementation . Pergamon, Kidlington, UK, 1996.

D. K. Merchant and G. L. Nemhauser. A model and an algorithm for the dynamic traffic assignment problems. Transportation Science , 12: 183–199, 1978.

D. K. Merchant and G. L. Nemhauser. Optimality conditions for a dynamic traffic assignment model. Transportation Science , 12: 200–209, 1978.

A. Nagurney. Computational comparisons of algorithms for general asymmetric traffic equilibrium problems with fixed and elastic demand. Transportation Research B , 20 (1): 78–83, 1986.

A. Nagurney. An equilibration scheme for the traffic assignment problem with elastic demand. Transportation Research B , 22 (1): 73–79, 1989.

G. L. Nemhauser, A. H. G. Rinnoy Kan, and M. J. Todd. Optimization , volume 1 of Handbooks in Operations Research and Management Science . North-Holland, Amsterdam, 1981.

M. Papageorgiou, editor. Concise Encyclopedia of Traffic and Transporation Systems , Oxford, UK, 1991. Pergamon Press.

M. Patriksson. The Traffic Assignment Problem , Models and Methods . VSP, Utrecht, NL, 1994.

S. H. Putman. Integrated urban models , volume 1. Pion limited, 207 Brondesbury Park, London NW2 5JN, 1983.

S. H. Putman. Integrated urban models , volume 2. Pion limited, 207 Brondesbury Park, London NW2 5JN, 1991.

B. Ran and D. Boyce. Modelling Dynamic Transportation Networks . Springer-Verlag, Heidelberg, Berlin, New York, 1996. Second edition.

K. Safwat and T. Magnanti. A combined trip generation, trip distribution, modal split and trip assignment model. Transportation Science , 22: 14–30, 1988.

A. Sen and T. E. Smith. Gravity Models of Spatial Interaction Behaviour . Springer-Verlag, Heidelberg, Berlin, New York, 1995.

Y. Sheffi. Urban Transportation Networks . Prentice-Hall, Englewood Cliffs, USA, 1985.

R. E. Tarjan. Data Structures and Network Algorithms . SIAM, Philadelphia, USA, 1983. CBMS-NSF, Regional Conference Series in Applied Mathematics.

H. Timmermans. Activity Based Approaches to Transportation Modelling . Pergamon, Kidlington, UK, 1996.

Ph. L. Toint and L. Wynter. Asymmetric multiclass assignment: a coherent formulation. In J. B. Lesort, editor, Transportation and Traffic Theory , pages 237–260, Oxford, U.K., 1996. Pergamon.

J. Wardrop. Some theoretical aspects of road traffic research. Proceedings of the Institute of Civil Engineers , part II , 1: 325–378, 1952.

F. V. Webster, P. H. Bly, and N. J. Paulley, editors. Urban Land-use and Transport Interaction , Policies and Models . Avebury, Aldershot, UK, 1988.

B. W. Wie, T. L. Friesz, and R. L. Tobin. Dynamic user optimal traffic assignment: a control theoretic formulation. presented at the US-Italy Joint Seminar on Urban Traffic Networks, Capri, 1989.

B. W. Wie, T. L. Friesz, and R. L. Tobin. Dynamic user optimal traffic assignment on congested multidestination networks. Transportation Research B , 24 (6): 431–442, 1990.

A. G. Wilson. Entropy in urban and regional modelling . Pion, London, 1970.

S. Yagar. Dynamic traffic assignment by individual path minimization and queing. Transportation Research , 5: 179–196, 1970.

S. Yagar. Emulation of dynamic equilibrium in traffic networks. In M. Florian, editor, Traffic equilibrium methods , New York, 1976. Springer-Verlag. Lecture Notes in Economics and Mathematical Systems 118.

Download references

Author information

Authors and affiliations.

Transportation Research Group Department of Mathematics, Facultés Universitaires ND de la Paix, B-5000, Namur, Belgium

Philippe L. Toint

You can also search for this author in PubMed   Google Scholar

Editor information

Editors and affiliations.

ISRO and SMG, Université Libre de Bruxelles, Boulevard du Triomphe, B-1050, Brussels, Belgium

Martine Labbé

Centre de Recherche sur les Transports, Université de Montréal, CP 6128, H3C 3JT, Montréal, Canada

Gilbert Laporte

Department of Transport Economics, Technical University of Budapest, Bertallan L. u. 2, H-1111, Budapest, Hungary

Katalin Tanczos

Département de Mathématiques, Université Notre Dame de la Paix, Rempart de la Vierge, 8, B-5000, Namur, Belgium

Philippe Toint ( ASI Director ) ( ASI Director )

Rights and permissions

Reprints and permissions

Copyright information

© 1998 Springer-Verlag Berlin Heidelberg

About this chapter

Toint, P.L. (1998). Transportation Modelling and Operations Research: A Fruitful Connection. In: Labbé, M., Laporte, G., Tanczos, K., Toint, P. (eds) Operations Research and Decision Aid Methodologies in Traffic and Transportation Management. NATO ASI Series, vol 166. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-03514-6_1

Download citation

DOI : https://doi.org/10.1007/978-3-662-03514-6_1

Publisher Name : Springer, Berlin, Heidelberg

Print ISBN : 978-3-642-08428-7

Online ISBN : 978-3-662-03514-6

eBook Packages : Springer Book Archive

Share this chapter

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Publish with us

Policies and ethics

• Find a journal
• Track your research

• Practice Mathematical Algorithm
• Mathematical Algorithms
• Pythagorean Triplet
• Fibonacci Number
• Euclidean Algorithm
• LCM of Array
• GCD of Array
• Binomial Coefficient
• Catalan Numbers
• Sieve of Eratosthenes
• Euler Totient Function
• Modular Exponentiation
• Modular Multiplicative Inverse
• Stein's Algorithm
• Juggler Sequence
• Chinese Remainder Theorem
• Quiz on Fibonacci Numbers

Transportation Problem | Set 1 (Introduction)

Transportation problem is a special kind of Linear Programming Problem (LPP) in which goods are transported from a set of sources to a set of destinations subject to the supply and demand of the sources and destination respectively such that the total cost of transportation is minimized. It is also sometimes called as Hitchcock problem.

Types of Transportation problems: Balanced: When both supplies and demands are equal then the problem is said to be a balanced transportation problem.

Unbalanced: When the supply and demand are not equal then it is said to be an unbalanced transportation problem. In this type of problem, either a dummy row or a dummy column is added according to the requirement to make it a balanced problem. Then it can be solved similar to the balanced problem.

Methods to Solve: To find the initial basic feasible solution there are three methods:

• NorthWest Corner Cell Method.
• Least Cost Method.
• Vogel’s Approximation Method (VAM).

Please Login to comment...

Similar reads.

• Mathematical

Improve your Coding Skills with Practice

What kind of Experience do you want to share?