liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Computation of Mileage Limits for Traveling Salesmen by Means of Optimization Techniques
Linköping University, Department of Mathematics.
2008 (English)Independent thesis Advanced level (degree of Magister), 20 points / 30 hpStudent thesis
Abstract [en]

Many companies have traveling salesmen that market and sell their products.This results in much traveling by car due to the daily customer visits. Thiscauses costs for the company, in form of travel expenses compensation, and environmentaleffects, in form of carbon dioxide pollution. As many companies arecertified according to environmental management systems, such as ISO 14001,the environmental work becomes more and more important as the environmentalconsciousness increases every day for companies, authorities and public.The main task of this thesis is to compute reasonable limits on the mileage ofthe salesmen; these limits are based on specific conditions for each salesman’sdistrict. The objective is to implement a heuristic algorithm that optimizes thecustomer tours for an arbitrary chosen month, which will represent a “standard”month. The output of the algorithm, the computed distances, will constitute amileage limit for the salesman.The algorithm consists of a constructive heuristic that builds an initial solution,which is modified if infeasible. This solution is then improved by a local searchalgorithm preceding a genetic algorithm, which task is to improve the toursseparately.This method for computing mileage limits for traveling salesmen generates goodsolutions in form of realistic tours. The mileage limits could be improved if theinput data were more accurate and adjusted to each district, but the suggestedmethod does what it is supposed to do.

Place, publisher, year, edition, pages
2008. , 61 p.
period traveling salesman problem, periodic, traveling salesman problem, ptsp, tsp, heuristic algorithm, mileage limit, business trips, travel expenses compensation
National Category
Mathematics Computational Mathematics
URN: urn:nbn:se:liu:diva-12473ISRN: LiTH-MAT-EX--08/08--SEOAI: diva2:200
Available from: 2008-10-15 Created: 2008-09-07 Last updated: 2008-10-15Bibliographically approved

Open Access in DiVA

fulltext(1852 kB)801 downloads
File information
File name FULLTEXT01.pdfFile size 1852 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
Department of Mathematics
MathematicsComputational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 801 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 425 hits
ReferencesLink to record
Permanent link

Direct link