Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • 91 views

    Operations Research Project On

    Uploaded by

    Sweta Dash
    This document presents a travelling salesman problem to optimize the route for a salesman visiting 5 cities in India and returning to the starting city of Bhopal. The problem is formulated as an integer program to minimize the total distance travelled. Different algorithms are discussed to solve this NP-hard problem, including brute force, branch and bound, and dynamic programming. The brute force solution finds the optimal route of 5816 km from Bhopal to Mumbai to Chennai to Bhubaneswar to Durgapur to New Delhi and back to Bhopal. Managerial insights are provided on applications of this optimization in various industries.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd

    Operations Research Project On

    Uploaded by

    Sweta Dash
    91 views12 pages
    This document presents a travelling salesman problem to optimize the route for a salesman visiting 5 cities in India and returning to the starting city of Bhopal. The problem is formulated as an integer program to minimize the total distance travelled. Different algorithms are discussed to solve this NP-hard problem, including brute force, branch and bound, and dynamic programming. The brute force solution finds the optimal route of 5816 km from Bhopal to Mumbai to Chennai to Bhubaneswar to Durgapur to New Delhi and back to Bhopal. Managerial insights are provided on applications of this optimization in various industries.

    Original Description:

    good

    Original Title

    Operations Research Project on (1)

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document presents a travelling salesman problem to optimize the route for a salesman visiting 5 cities in India and returning to the starting city of Bhopal. The problem is formulated as an integer program to minimize the total distance travelled. Different algorithms are discussed to solve this NP-hard problem, including brute force, branch and bound, and dynamic programming. The brute force solution finds the optimal route of 5816 km from Bhopal to Mumbai to Chennai to Bhubaneswar to Durgapur to New Delhi and back to Bhopal. Managerial insights are provided on applications of this optimization in various industries.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    91 views12 pages

    Operations Research Project On

    Uploaded by

    Sweta Dash
    This document presents a travelling salesman problem to optimize the route for a salesman visiting 5 cities in India and returning to the starting city of Bhopal. The problem is formulated as an integer program to minimize the total distance travelled. Different algorithms are discussed to solve this NP-hard problem, including brute force, branch and bound, and dynamic programming. The brute force solution finds the optimal route of 5816 km from Bhopal to Mumbai to Chennai to Bhubaneswar to Durgapur to New Delhi and back to Bhopal. Managerial insights are provided on applications of this optimization in various industries.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    of 12

    Operations research Project on

    Travelling Salesman Problem

    To devise a strategy and plan out efficient routes for


    travelling between a number of cities which optimizes time
    and related costs using Travelling Salesman Approach.

    Presented By:
    Ajita Gupta (UM18005)
    Akanksha Sreen (UM18006)
    Gaurav Singh (UM18)
    Debjit Ghosh(UM18)
    Sakshi Mudey (UM18050)
    Vijay Kashyap (UM18037)
    PROBLEM FORMULATION

    Rajiv is a salesman who works in Aggrawal construction


    company, Bhopal. He needs to travel 5 cities (New Delhi,
    Mumbai, Durgapur, Chennai, Bhubaneswar) for selling
    flats and then return back to Bhopal, but he doesn’t want to
    touch a city twice. Also he wants to minimize the distance
    covered. Formulate a path for him as per given conditions.

    Variable: Distance

    Assumption:
    Minimizing distance will lead us on
    Minimizing our cost as well as time.
    DATA SET

    CITIES Bhopal New Delhi Durgapur Chennai Mumbai Bhubaneswar

    Bhopal 0 695 1204 1475 775 1189

    New Delhi 695 0 1302 2190 1405 1682

    Durgapur 1204 1302 0 1709 1977 482

    Chennai 1475 2190 1709 0 1334 1228

    Mumbai 775 1405 1977 1334 0 1766

    Bhubaneswar 1189 1682 482 1228 1766 0

    Distances are in kms


    SOLUTION

    Methods to solve TSP


     Brute force approach

     Branch and bound

     Dynamic programming

     Heuristic Algorithms

     Simulated Annealing

     Neural Network

     Ant Colony Optimization


    Problem formulation

    We let the n selected cities in the salesman's tour be the set of vertices V of a graph. The set of
    edges E of the graph corresponds to the different connections between each city. Since we can travel
    from any city to another, the graph is complete. That is, there is an edge between every pair of nodes.
    For each edge in the graph we associate a binary variable

    Since the edges are undirected, we have that xij=xji, and it suffices to only include edges with i<j in
    model. We want to minimize the total distance travelled during the tour. Therefore, we calculate the
    distance dij between each pair of nodes i and j. The total distance travelled is then the sum of the
    distances of the edges included in the tour
    The tour should only pass through each city once. Therefore, each node in the graph should have
    exactly one incoming edge and one outgoing edge. In other words, for every node i exactly two of
    the xij binary variables should be equal to 1. We write this constraint as

    This constraint means that the salesman should enter and leave each city exactly once
    To eliminate the sub tours we add the following constraints

    Finally the integer program formulation becomes


    SOLUTION (BRUTE FORCE APPROACH)
    BHOPAL

    NEW DELHI DURGAPUR CHENNAI MUMBAI BHUBANESWAR

    NEW DELHI DURGAPUR CHENNAI BHUBANESHWAR

    NEW DELHI DURGAPUR BHUBANESHWAR

    NEW DELHI BHUBANESHWAR

    NEW DELHI

    BHOPAL
    SOLUTION(BRANCH & BOUND)

    STEP 1
    STEP 3 STEP 5
    Drawing a table and .
    Branching & Locating the knot with
    reduction of it Etiquette the smallest etiquette
    calculating

    STEP 2 STEP 4
    The calculation of the Drawing the
    lower boundary branching tree
    SOLUTION
    RESULT

    BHOPAL MUMBAI CHENNAI BHUBANESWAR DURGAPUR NEW DELHI BHOPAL

    5816 kms
    Managerial Insights
    Solution will be helpful for New diversity of Identification of problem and statement holds
    Product Lines and tremendous increase in utmost importance with aspect of
    complexity of Production Planning management insights.

    Insights of this solution will come in hand for


    Yield Management systems could be used to
    problems in Gas Pipeline and Petroleum
    boost revenue
    pipeline construction.

    Airlines too could use optimization of distance Utilization of operating rooms and personnel .
    which could help in fuel consumption Assessing the risk posed by patients with
    reduction. various medical conditions.

    Insights could also be used in service base Credit risk management and automation in
    industry for optimization of resources. electronic circuit.

    You might also like