Phương pháp tối ưu đàn kiến giải bài toán
trình tự xe

Đinh Thị Hằng

Trường Đại học Công nghệ
Luận văn ThS Chuyên ngành: Hệ thống thông tin; Mã số 60 48 01 04
Người hướng dẫn: PGS.TS. Hoàng Xuân Huấn
Năm bảo vệ: 2014 Keywords. Phương pháp tối ưu đàn kiến; Tối ưu tổ hợp; ài toán trình tự xe; Công nghệ
thông tin.
9

MỞ ĐẦU
Trong quá trình sn xut ra sn phm thì vic lp k hoch sn xut là cc
k quan trng, nó ng trc tip ti hiu sut ca h thng máy móc và
nh ng n cht lng ca toàn b quá trình sn xuc bit ngày
nay khi mà quy mô sn xut ln, vich sn xut hp lý càng có ý
ng, thc t vic lp k hoch sn xut là không h n và
không th ch n da trên kinh nghim. Chính vì  c t
n hành nghiên cu bài toán trình t xe t  1986 nhm m
s hóa bài toán và xây dng li gii trên máy tính nhm gim thiu thi gian sn
xut m bc ng làm vic ca các trm sn xut không tn quá
nhiu chi phí (ràng buc v ng mang li hiu qu v kinh t 
sut. Bài toán c s chú ý quan tâm ca o gii chuyên môn
và à bài toán NP-khó trong

thi các thut toái gian thc hi phi x
lý tìm kic nghiy, nu thi gian và s
ng vòng lp hn ch thì thut toán cho chng li gii tt nht và
hi t nhanh nht là ACO1+2, nu thi gian không hn ch thì thut toán cho
chng li gii tt nht là TSIACOLS.
Ni dung chính trong bài lua tôi g
Chƣơng 1:Gii thiu v bài toán t hp tng quát và bài toán trình t xe,
các cách tip cn gii bài toán.
Chƣơng 2:Gii thin, lch s và phát trin.
pháp ti chào hàng.
Chƣơng 3:Trình bày các  ACO gii bài toán trình t xe.
Chƣơng 4: Tin hành chy thc nghib d liu chun,
thng kê kt qu c và so sánh gia các thut toán ACO.
75

TÀI LIỆU THAM KHẢO
Tiếng Việt
1.  ), Phương pháp tối ưu đàn kiến và ứng dụng, Lun án ti
ngh -
Tiếng Anh
2. Christine Solnon (2008), Combining two Pheromone Structures forSolving the Car
Sequencing Problem with AntColony Optimization, Preprint submitted to Elsevier
Science
3. M. Dorigo, and T.Stützle (2004), Ant Colony Optimization, The MIT Press,
Cambridge, Masachusetts.
4. M. Dorigo, V. Maniezzo and A. Colorni (1991), The Ant System: An autocatalytic
optimizing process, Technical Report 91-016 Revised, Dipartimento di Elettronica,
Politecnico di Milano, Milano, Italy.
5. M. Dorigo (1992), Optimization, learning and natural algorithms, PhD. dissertation,
Milan Polytechnique, Italy.

17. [Kis, 2004] T. Kis. On the complexity of the car sequencing problem. Operations
Research Letters, 32:331335, 2004.
18. [DSvH88] M. Dincbas, H. Simonis, and P. van Hentenryck. Solving the carsequencing
problem in constraint logic programming. In Y. Kodratoff, editor, Proceedings of
ECAI-88, pages 290295, 1988.
19. [GW99] I.P. Gent and T. Walsh. Csplib: a benchmark library for constraints.
Technical report, APES-09-1999, 1999. available from A
shorter version appears in CP99.
20. [Tsa93] E.P.K. Tsang. Foundations of Constraint Satisfaction. Academic Press,
London, UK, 1993.
21. [RP97] J C. Regin and J F. Puget. A filtering algorithm for global sequencing
constraints. In CP97, volume 1330 of LNCS, pages 3246. SpringerVerlag, 1997.
22. [LLW98] J.H.M. Lee, H.F. Leung, and H.W. Won. Performance of a comprehensive
and efficient constraint library using local search. In 11th Australian JCAI, LNAI.
Springer-Verlag, 1998.
23. Introduction to Machine Learning, Massachusetts Institute
of Technology, Second Edition.
24. [Sol00] C. Solnon. Solving permutation constraint satisfaction problems with
artificial ants. In Proceedings of ECAI’2000, IOS Press, Amsterdam, The
Netherlands, pages 118122, 2000.