An algorithm for the traveling salesman problem with pickup and delivery customers (Q1071656): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Added link to MaRDI item.
links / mardi / namelinks / mardi / name
 

Revision as of 00:23, 31 January 2024

scientific article
Language Label Description Also known as
English
An algorithm for the traveling salesman problem with pickup and delivery customers
scientific article

    Statements

    An algorithm for the traveling salesman problem with pickup and delivery customers (English)
    0 references
    0 references
    0 references
    0 references
    1985
    0 references
    This paper considers the traveling salesman problem with \(2n+1\) cities of which one is a depot, n are pickup points and n are corresponding delivery points. Each possible trip by a salesman from one city to another is represented by an arc of a network to which a cost is allocated. A feasible tour is defined as one in which the salesman starts at the depot, visits all other cities exactly once without travelling to a delivery point before its corresponding pickup point is visited and then returns to the depot. The objective is find a feasible tour for which the total cost of arcs used is a minimum. A lower bound is obtained by selecting the minimum element in each row of the cost matrix and reducing every element in that row by this constant. The matrix is further reduced by applying an identical procedure to the columns. The lower bound is given by the sum of these reducing constants. When some arcs of the tour are known, several results are derived which exclude certain other arcs from a feasible tour; the costs for excluded arcs are set to infinity. A branch and bound algorithm is proposed and computational results for problems with up to 18 pickup and delivery points are provided. A generalization is given to the capacitated problem in which the quantity to be collected at each pickup point is specified and the total quantity carried at any time cannot exceed the vehicle capacity. Also, a generalization to the case that there are several salesmen to perform the pickups and deliveries is given.
    0 references
    0 references
    traveling salesman
    0 references
    depot
    0 references
    pickup points
    0 references
    delivery points
    0 references
    lower bound
    0 references
    branch and bound algorithm
    0 references
    computational results
    0 references
    capacitated problem
    0 references
    vehicle capacity
    0 references
    several salesmen
    0 references

    Identifiers