Sử dụng thuật toán heuristic để tối ưu bài toán giao hàng :Hội nghị khoa học trẻ lần 4

Hội nghị Khoa học trẻ lần 4 năm 2022 (YSC2022) – IUH

Ngày 14/10/2022 ISBN: 978-604-920-155-4

© 2022 Trường Đại học Công nghiệp Thành phố Hồ Chí Minh 371

YSC4F.233

SỬ DỤNG THUẬT TOÁN HEURISTIC ĐỂ TỐI ƯU BÀI TOÁN GIAO HÀNG

LÂM NGỌC LONG, VÕ HOÀNG TUẤN, NGUYỄN ĐÌNH THANH, HỒ HOÀNG VÂN ANH,

ĐOÀN QUỐC HUY , LÊ PHÚC LỮ

Khoa Công nghệ Thông tin, Trường Đại học Công nghiệp Thành phố Hồ Chí Minh

[email protected], [email protected], [email protected]

[email protected], [email protected], [email protected]

Tóm tắt. Trong bối cảnh hiện nay, mỗi khi các shipper nhận được các đơn hàng thì họ phải chọn ra tuyến

đường phù hợp để giao hàng theo yêu cầu. Ứng dụng được sử dụng thường xuyên là dựa trên nền tảng

Openstreetmap API để tìm đường đi giữa hai địa điểm. Tuy nhiên, công nghệ này chưa giải quyết triệt để

bài toán tìm đường đi qua nhiều địa điểm sao cho tổng quãng đường là ngắn nhất và hạn chế được việc lặp

lại đường đã đi càng nhiều càng tốt. Vì vậy, nhóm đề xuất sử dụng thuật toán heuristic là 2-OPT (2-Optional

Practical Training) để tìm ra một phương án tối ưu mang tính địa phương trong thời gian thực. Bài nghiên

cứu sẽ được thực hiện dựa trên các tuyến đường của Thành phố Hồ Chí Minh và trực quan hóa dữ liệu lên

Openstreetmap sử dụng các API được hỗ trợ sẵn.

Từ khóa. shipper, 2-opt, google map API, giao hàng nhanh, bài toán người giao hàng, thuật toán heuristic.

USING THE HEURISTIC ALGORITHM TO OPTIMIZE THE DELIVERY PROBLEM

Abstract. Nowadays, whenever a shipper receives some orders, he must choose the appropriate routes to

deliver as required. The popular used by the delivery shippers is based on the Openstreetmap API. However,

it has not fully solved the problem of finding the way among multiple destinations minimizing the total

travelling distance also limiting the repetition of the route traveled as much as possible. So our team studies

the use of one heuristic algorithm, which is 2-OPT (2-Optional Practical Training) to find out the local

optimal in real time. This research will focus on the routes of Ho Chi Minh City and visualized the data on

Openstreetmap using the supported API.

Keywords. shipper, 2-opt, google map API, fast delivery, travelling salesman problem, heuristic

algorithm.

1. ĐẶT VẤN ĐỀ

1.1. Giới thiệu

Tại [1], bản đồ trực tuyến đang được sử dụng ngày càng rộng rãi trong nhiều lĩnh vực, đặc biệt là trong việc

tìm đường và đánh dấu các địa danh lên trên bản đồ. Nó không chỉ được sử dụng nhiều trong các giao diện

website mà còn được dùng nhiều trong các ứng dụng điện thoại. Người dùng không chỉ dễ dàng tìm kiếm

địa chỉ và định vị được vị trí mà còn có thể tìm kiếm được đường đi nhanh chóng từ nơi họ đứng đến địa

điểm cần tìm một cách nhanh chóng, chính xác.