Bài toán tìm đường đi của người giao hàng

MỞ ĐẦUBài toán người giao hàng tiếng Anh: travelling salesman problem - TSP là một bài toán NP-khó Một bài toán A được gọi là NP- khó NP-hard nếu như sự tồn tại thuật toán đa th

NHẬN XÉT CỦA GIÁO VIÊN

PHỤ LỤC

MỞ ĐẦU

Bài toán người giao hàng (tiếng Anh: travelling salesman problem - TSP) là một bài

toán NP-khó ( Một bài toán A được gọi là NP- khó (NP-hard) nếu như sự tồn tại thuật toán

đa thức để giải nó kéo theo sự tồn tại thuật toán đa thức để giải mọi bài toán trong

NP .) thuộc thể loại tối ưu rời rạc hay tổ hợp được nghiên cứu trong vận trù

học hoặc lý thuyết khoa học máy tính Bài toán được phát biểu như sau Cho trước

một danh sách các thành phố và khoảng cách giữa chúng, tìm chu trình ngắn nhất thăm mỗi thành phố đúng một lần

Bài toán được nêu ra lần đầu tiên năm 1930 và là một trong những bài toán được nghiên cứu sâu nhất trong tối ưu hóa Nó thường được dùng làm thước đo cho nhiều phương pháp tối ưu hóa Mặc dù bài toán rất khó giải trong trường hợp tổng quát, có

nhiều phương pháp giải chính xác cũng như heuristic đã được tìm ra để giải quyết một

số trường hợp có tới hàng chục nghìn thành phố

Ngay trong hình thức phát biểu đơn giản nhất, bài toán TSP đã có nhiều ứng dụng trong lập kế hoạch, hậu cần, cũng như thiết kế vi mạch

Trong lý thuyết độ phức tạp tính toán, phiên bản quyết định của TSP (cho trước độ

dài L, xác định xem có tồn tại hay không một chu trình đi qua mỗi đỉnh đúng một lần

và có độ dài nhỏ hơn L) thuộc lớp NP-đầy đủ ( Một bài toán quyết định A được gọi là NP-đầy đủ (NP-Complete) nếu A là một bài toán trong NP hay mọi bài toán trong NP đều có thể quy dẫn về A ) Do đó, có nhiều khả năng là thời gian xấu nhất của bất kì thuật toán nào

cho TSP đều tăng theo cấp số nhân với số thành phố

I TỔNG QUAN VỀ BÀI TOÁN NGƯỜI GIAO HÀNG (travelling salesman

problem - TSP)

1.Lịch sử bài toán người giao hàng

Nguồn gốc của bài toán người bán hàng vẫn chưa được biết rõ Một cuốn sổ tay dành cho người bán hàng xuất bản năm 1832 có đề cập đến bài toán này và có ví dụ cho chu trình trong nước Đức và Thụy Sĩ, nhưng không chứa bất kì nội dung toán học nào Bài toán người bán hàng được định nghĩa trong thế kỉ 19 bởi nhà toán học

Ireland William Rowan Hamilton và nhà toán học Anh Thomas Kirkman Trò chơi

Icosa của Hamilton là một trò chơi giải trí dựa trên việc tìm kiếm chu trình

Hamilton Trường hợp tổng quát của TSP có thể được nghiên cứu lần đầu tiên bởi các

nhà toán học ở Vienna và Harvard trong những năm 1930, đặc biệt là Karl Menger,

người đã định nghĩa bài toán, xem xét thuật toán hiển nhiên nhất cho bài toán, và phát hiện ra thuật toán láng giềng gần nhất là không tối ưu

Hassler Whitney ở đại học Princeton đưa ra tên bài toán người bán hàng ngay sau

đó

Trong những năm 1950 và 1960, bài toán trở nên phổ biến trong giới nghiên cứu khoa

học ở Châu Âu và Mỹ George Dantzig, Delbert Ray Fulkerson và Selmer

M.Johnson ở công ty RAND tại Santa Monica đã có đóng góp quan trọng cho bài

toán này, biểu diễn bài toán dưới dạng quy hoạch nguyên và đưa ra phương pháp mặt

phẳng cắt để tìm ra lời giải Với phương pháp mới này, họ đã giải được tối ưu một

trường hợp có 49 thành phố bằng cách xây dựng một chu trình và chứng minh rằng không có chu trình nào ngắn hơn Trong những thập niên tiếp theo, bài toán được nghiên cứu bởi nhiều nhà nghiên cứu trong các lĩnh vực toán học, khoa học máy tính, hóa học, vật lý, và các ngành khác

Năm 1972, Richard M Karp chứng minh rằng bài toán chu trình Hamilton là

NP-đầy đủ, kéo theo bài toán TSP cũng là NP-NP-đầy đủ Đây là một lý giải toán học cho sự

khó khăn trong việc tìm kiếm chu trình ngắn nhất

Một bước tiến lớn được thực hiện cuối thập niên 1970 và 1980 khi Grötschel, Padberg, Rinaldi và cộng sự đã giải được những trường hợp lên tới 2392 thành phố, sử dụng

phương pháp mặt phẳng cắt và nhánh cận.

Trong thập niên 1990, Applegate, Bixby, Chvátal, và Cook phát triển một chương trình mang tên Concorde giải được nhiều trường hợp có độ lớn kỉ lục hiện nay.

Gerhard Reinelt xuất bản một bộ dữ liệu các trường hợp có độ khó khác nhau mang

tên TSPLIB năm 1991, và nó đã được sử dụng bởi nhiều nhóm nghiên cứu để so sánh

kết quả Năm 2005, Cook và cộng sự đã giải được một trường hợp có 33810 thành

phố, xuất phát từ một bài toán thiết kế vi mạch Đây là trường hợp lớn nhất đã được

giải trong TSPLIB Trong nhiều trường hợp khác với hàng triệu thành phố, người ta đã

tìm được lời giải với sai số không quá 1% so với lời giải tối ưu

2 Phát biểu của bài toán người giao hàng

Có một người giao hàng cần đi giao hàng tại n thành phố Xuất phát từ một thành phố

nào đó, đi qua các thành phố khác để giao hàng và trở về thành phố ban đầu Mỗi thành phố chỉ đến một lần, khoảng cách từ một thành phố đến các thành phố khác là xác định được Hãy tìm một chu trình (một đường đi khép kín thỏa mãn điều kiện trên) sao cho tổng độ dài các cạnh là nhỏ nhất

Hiện nay, có rất nhiều giải thuật khác nhau nhằm mục đích giải quyết bải toán TSP,

trong đó phải kể đến các giải thuật như: Quy hoạch động (Dynamic Programming),

giải thuật di truyền (Genetic Algorithm - GA), giải thuật luyện thép (Simulated

Annealing - SA) ,giải thuật đàn kiến (Ant Colony Optimization - ACO), giải thuật trí

tuệ bầy đàn (Particle Swarm Optimization - PSO), giải thuật nhánh cận (A branch-and-bound)…Và nội dung của bài báo niên luận này sẽ chỉ đề cập tới việc sử dụng

giải thuật nhánh cận để giải quyết bài toán TSP

II GIẢI THUẬT NHÁNH CẬN (A branch-and-bound)

1 Tìm hiểu về giải thuật nhánh cận

Trong các phương pháp giải bài toán quy hoạch nguyên, phương pháp nhánh cận là

một trong các phương pháp có hiệu quả Phương pháp nhánh cận được Land A.H và Doig A.G xây dựng năm 1960 giải bài toán qui hoạch nguyên, đến 1963 được Little J.D, Murty K.G, Sweeney D.W và Karen C sử dụng thành công giải bài toán người du

lịch Năm 1979 Giáo sư Hoàng Tụy đã ứng dụng rộng rãi để giải các bài toán tối ưu

khó

Phương pháp nhánh cận là phương pháp chủ yếu để giải các bài toán tối ưu tổ hợp Tư tương cơ bản của thuật toán là xây dựng cây tìm kiếm phương án tối ưu, nhưng không xây dựng toàn bộ cây mà sử dụng giá trị cận để hạn chế bớt các nhánh

Cây tìm kiếm phương án có nút gốc biểu diễn cho tập tất cả các phương án có thể có,

mỗi nút lá biểu diễn cho một phương án nào đó Nút n có các nút con tương ứng với các khả năng có thể lựa chọn tập phương án xuất phát từ n.

Với mỗi nút trên cây ta sẽ xác định một giá trị cận Giá trị cận là một giá trị gần với giá của phương án Với bài toán tìm min ta sẽ xác định cận dưới còn với bài toán tìm max ta sẽ xác định cận trên Cận dưới là giá trị nhỏ hơn hoặc bằng giá của phương án, ngược lại cận trên là giá trị lớn hơn hoặc bằng giá của phương án

2 Áp dụng thuật toán nhánh cận cho bài toán TSP

a) Bài toán

Có một người giao hàng cần đi giao hàng tại n thành phố T 1 …T n Xuất phát từ một thành phố nào đó, người giao hàng cần đi qua tất cả các thành phố còn lại, mỗi thành phố đi qua đúng một lần rồi quay trở lại thành phố xuất phát

Gọi C ij là chi phí đi từ thành phố T i đến T j Hãy tìm một hành trình thỏa yêu cầu bài toán sao cho chi phí là nhỏ nhất

b) Ý tưởng

Gọi π là một hoán vị của {1…n} thì một hành trình thỏa yêu cầu bài toán co

dạng: T π(1) => T π(2) =>… => T π(n).

Nên co tất cả n! hành trình như thế Ta cố định một thành phố xuất phát T 1 thì co (n-1)! hành trình.

Lúc này, bài toán được quy về bài toán tìm Min{f(a 2,…, a n ) : (a 2,…, a n ) là hoán vị của {2,…,n}} Với f(a 1 ,…, a n ) = C1,a2 + Ca a2, 3 + + Ca n−1,a n + Ca n,1

c) Thiết kế

Input: C = (Cij)

Output: x* = (x1,…,xn) //Hành trình tối ưu

f* = f(x*) //Giá trị tối ưu

Try(i) =

For (j=1  n)

If (Chấp nhận được) {

Xác định xi theo j;

Ghi nhận trạng thái mới;

If (i==n)

Cập nhật lời giải tối ưu;

Else {

Xác định cận g(x1,…,xi);

If (g(x1,…,xi) ≤ f*)

Try (i+1);

}

//Trả bài toán về trạng thái cu

} Nếu ta cố định xuất phát từ T1, thì phải duyệt vòng lặp từ j=2

Đặt: CMin = Min{Cij: i, j ϵ {1, ,n}}

Giả sử vào bước i ta tìm được lời giải bộ phận cấp i là (x1, ,xi), tức là đã đi qua đoạn đường T1  T2 … Ti, tương ứng với chi phí:

Si = 1 2 2 3 1

−

Để phát triển hành trình bộ phận này thành một hành trình đầy đủ, ta còn phải đi qua n-i+1 đoạn đường nữa, gồm n-i thành phố còn lại và đoạn quay lại T1

Do chi phí mỗi một trong n-i+1 đoạn còn lại không nhỏ hơn CMin, nên hàm đánh giá cận có thể xác đinh như sau:

g(x1,…,x2) = Si + (n-i+1)CMin

Điều kiện chấp nhận được của j là thành phố Tj chưa đi qua

Ta sử dụng một mảng logic để biểu diễn cho trạng thái trên

Daxet[j] =

Mảng Daxet[] phải được bằng 0 tất cả

Xác định xi theo j bằng câu lệnh gán: xi=j

Cập nhật trạng thái mới: Daxet[j]=1

Cập nhật lại chi phí sau khi tìm được xi: S = S + Cx x i1 i

−

Cập nhật lời giải tối ưu:

Chi phí hành trình vừa tìm được: Tong = S + C x n1;

Nếu (Tong < f*) thì

Lgtu=x;

f* = Tong;

Thao tác hủy bỏ trạng thái : Daxet[j]=0

Trả lại chi phí cũ: S = S - Cx x i1 i

−

Thủ tục nhánh cận viết lại như sau:

Try(i) =

For (j=2  n)

If (!Daxet[j]) {

x[i] = j;

Daxet[j] = 1;

S = S + C[x[i-1]][x[i]];

If (i==n) //Cập nhật tối ưu

{

Tong = S + C[x[n]][x[1]]];

If(Tong <f*) {

Lgtu=x;

f* = Tong;

} }

Else {

g = S + (n-i+1)*CMin; //Đánh giá cận

If (g < f*)

Try (i+1);

}

S = S - C[x[i-1]x[i]];

Daxet[j]=0;

}

III CHƯƠNG TRÌNH DEMO

1 Một số chương trình con

Chương trình sẽ lấy dữ liệu đầu vào từ một file *.txt Nội dung của file này bao

gồm số thành phố và một ma trận vuông biểu diễn khoảng cách giữa các thành phố

Lưu đồ:

Begin

i<=n;

j<=n i=1; j=1

Tăng i, j lên 1

Nhập n, C[i][j]

In C[i][j]

Dữ liệu được lấy

từ trong tập tin dulich.txt.

Sai

Đúng g

Code của chương trình:

void Read_Data(){

int i,j;

FILE *fp;

fp=fopen("d:\\dulich.txt","r");

fscanf(fp,"%d",&n);

printf("\n\t So thanh pho:%d",n);

printf("\n\n \tMa tran chi phi:\n");

for(i=1;i<=n;i++){

printf("\n");

for(j=1;j<=n;j++){

fscanf(fp,"\t%d",&C[i][j]);

printf("\t%5d",C[i][j]);

} } }

b) Tính cận dưới:

- Cận dưới tại mỗi nút là một số nhỏ hơn hoặc bằng giá của tất cả các phương án được biểu diễn bởi nút đó Giá của một phương án ở đây là tổng độ dài của một chu trình

- Cận dưới cho nút gốc, mỗi đỉnh ta chọn hai cạnh có độ dài nhỏ nhất từ ma trận

- Cận dưới của nút gốc bằng tổng độ dài tất cả các cạnh được chọn chia cho 2

- Đối với các nút khác, chúng ta phải lựa chọn hai cạnh có độ dài nhỏ nhất thỏa điều kiện ràng buộc (phải chứa cạnh này, không chứa cạnh kia)

Lưu đồ :

Begin

i<>j && min > C[i][j]

Tăng i, j lên 1

end

In min

min =1000, i =1, j = 1

i<=n; j<=n

min = C[i][j]

Sai

Đúng

Sai Đúng

Code của chương trình :

int Min_Matrix(){

int min=1000, i, j;

for(i=1;i<=n;i++){

for(j=1;j<=n;j++) { if(i!=j&&min>C[i][j]) min=C[i][j];

} } return (min);

}

c) Chương trình hoàn chỉnh

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#include <io.h>

#define Max 20 int n, P[Max], B[Max], C[20][20], count=0;

int A[Max], Xopt[Max];

int Can, Cmin, Fopt;

void Read_Data(){ //Đọc dữ liệu đầu vào từ file *txt

int i,j;

FILE *fp;

fp=fopen("d:\\giaohang.txt","r");

fscanf(fp,"%d",&n);

printf("\n\t So thanh pho:%d",n);

printf("\n\n \tMa tran chi phi:\n");

for(i=1;i<=n;i++){

printf("\n");

for(j=1;j<=n;j++){

fscanf(fp,"\t%d",&C[i][j]);

printf("\t%5d",C[i][j]);

} } } int Min_Matrix(){

int min=1000, i, j;

for(i=1;i<=n;i++){

for(j=1;j<=n;j++) { if(i!=j&&min>C[i][j]) min=C[i][j];

} } return (min);

}

int i;

Cmin=Min_Matrix();

Fopt=32000;Can=0;A[1]=1;

for(i=1;i<=n;i++)

B[i]=1;

} void Result(){ //Tính toán và trả về kết quả

int i;

printf("\n\n\t Hanh trinh toi uu :%d",Fopt);

printf("\n\n\t Hanh trinh:");

for(i=1;i<=n;i++) printf("%3d->",Xopt[i]);

printf("\t%d",1);

printf("!!!!!");

}

int i;

for (i=1;i<=n;i++) Xopt[i]=A[i];

} void Update_Kyluc(){ //Cập nhật

int sum;

sum=Can+C[A[n]][A[1]];

if(sum<Fopt){

Swap();

Fopt=sum;

} }

void Try(int i){ //Hàm thư

int j;

for (j=2;j<=n;j++){

if(B[j]){

A[i]=j;B[j]=0;

Can=Can+C[A[i-1]][A[i]];

if(i==n) Update_Kyluc();

else if(Can+(n-i+1)*Cmin<Fopt){

count ++;

Try(i+1);

} B[j]=1;Can=Can-C[A[i-1]][A[i]];

} } } int main(){

system("cls");

Read_Data();

Init();

Try(2);Result();

getch();

}

2 Ví dụ minh họa

Cho ma trận chi phí : C =

3 14 18 15

∞

Áp dụng giải thuật nhánh cận bằng tay

Phương án tối ưu

(1,2,3,4,5)

S=35; g=37

(1,2,3,5,4) S=16; g=18

(1,2,3)

S=7; g=13

(1,2,4) S=25; g = 31

(1,2,5) S=23; g=29

(1,2,3,5) S=11; g=15

(1,2,3,4)

S=23; g=27

(1) f* =

(1,2) S=3; g=11

(1,3) S=14; g = 2

(1,4) S=18; g = 26

(1,4) S=15; g=23

Cắt tỉa do g ≥ f* (f* = 22)

Bài toán được thực hiện trên chương trình :

IV KẾT LUẬN

1 Ưu điểm

- Về cơ bản đã khái quát bài toán TSP và giải thuật nhánh cận giải quyết bài toán

- Ứng dụng giải thuật nhánh cận tạo được chương trình đơn giản tính toán giải quyết các bài toán TSP nhỏ

2 Những hạn chế

- Áp dụng thuật toán nhạnh cận giải quyết được các bài toán TSP trên mặt lý

thuyết nhưng cài đặc giải thuật vào chương trình thì còn rất khó khăn

- Vẫn còn thiếu một số lưu đồ của một số chương trình con

- Chương trình vẫn chưa cho kết quả được ở dạng đồ họa

…

3 Hướng phát triển của đề tài

- Cố gắng hiểu rõ hơn về kỹ thuật nhánh cận cũng như việc cài đặt giải thuật

- Khắc phục các lỗi còn thiếu sót của chương trình như giao diện đồ họa

V NGUỒN THAM KHẢO

 Giáo trình giải thuật - Nguyễn Văn Linh.

 Thiết kế và đánh giá thuật toán – Trần Tuấn Minh.

 Giải thuật và lập trình – Lê Minh Hoàng.

 Thuật toán nhánh cận – Bùi Thế Tâm.

 Kỹ thuật lập trình C – Đại học Hàng hải.

 Giáo trình đồ họa trong C

 Branch and Bound Algorithms for TSP – YouTube

 Hướng dẫn cấu hình Đồ họa cho Dev-Cpp – YouTube

 Tài liệu từ wikipedia.org

 Báo cáo niên luận - Nguyễn Trung Tính.

 Các Topic về phương pháp nhánh cận

Link1:http://svictu.com/forum/index.php?threads/ph%C6%B0%C6%A1ng-pha

%CC%81p-nha%CC%81nh-c%C3%A2%CC%A3n.104/

Link2: http://khmt.123.st/t168-topic

Link3: http://diendan.congdongcviet.com/showthread.php?t=2508

Link4:http://wiki.answers.com/Q/Could_you_give_the_C_code_for_travelling_sal

esman_problem_using_branch_and_bound

…