The asymmetric travelling salesman problem and a reformulation of the Miller-Tucker-Zemlin constraints

Article Abstract:

The asymmetric travelling salesman problem (ATSP) in a loop-free directed graph G = (V,A) where V - {1,...,n} and costs cij for each arc (i,j) E involves deriving the least cost hamiltonian circuit contained in the graph. Several known formulations for the asymmetric travelling salesman problem (ATSP) are well known. Relationships between the linear programming relaxations of some old and new extended formulations for the ATSP are compared in deriving a compact formulation whose LP relaxation is characterized by a given set of circuit inequalities.

Models, Evaluation, Scheduling (Management), Mathematical models, Numerical calculations

---

A classification of formulations for the (time-dependent) traveling salesman problem

Article Abstract:

Several formulations of the time-dependent traveling salesman problem are investigated with respect to older versions of the classical problem. The formulations include one based on a linearized quadratic assignment model and 3-index formulations based on the work of J.C. Picard, M. Queyranne, K.R. Fox, B. Gavish and S. Graves. The problem, which has many real-world applications, pertains to situations where arc costs are 'dependent on their position in the tour.'

---

A new extension of local search applied to the Dial-A-Ride problem

Article Abstract:

The concept of local search, a heuristic for solving combinatorial optimization problems, is developed. To this end, a new technique, known as sacrificing, is introduced to enhance the conventional local improvement algorithm without compromising its running time. This improvement can be seen in the derived solutions for the Dial-A-Ride problem, another version of the Traveling Salesman problem.

Heuristic programming

Similar abstracts:

• Abstracts: Drivers of supply network governance: an explorative study of the Dutch chemical industry. Sharing sensitive information supply relationships: the flaws in one-way open-book negotiation and the need for transparency
• Abstracts: Obstacles to reforming the UN: interests of developed and developing countries clash. Is UN declaration universal?
• Abstracts: Government incentives and the financial services sector in Scotland. A select replication of the Cecchini microeconomic methodology on the EFTA financial services sectors: a note and critique
• Abstracts: British expatriate service provision in Spain's Costa del Sol. International trade in producer services: alternative explanations
• Abstracts: An exact algorithm for the capacitated facility location problems with single sourcing. A method for the cutting stock problem with different qualities

This website is not affiliated with document authors or copyright owners. This page is provided for informational purposes only. Unintentional errors are possible.