Việc thực hiện tốt nhất trường hợp sử dụng định tuyến xe/bán xe du lịch

Question

Gần đây, tôi đã gặp một trường hợp trong cuộc phỏng vấn khi trường hợp sử dụng được yêu cầu giải quyết thuộc về vấn đề định tuyến xe. Tôi đã có thể cho họ biết vấn đề thực tế là gì và toán học nào liên quan đến vấn đề này. Tôi đã giải thích cách sử dụng trường hợp sử dụng dưới đây cũng có thể được giải quyết bằng cách sử dụng phần mô hình MapReduce của Hadoop. (giải thích làm thế nào nhiều bản đồ giảm công việc sẽ có thể giải quyết vấn đề) bằng cách sử dụng thuật toán đồ thị được đề cập trong cuốn sách này xử lý văn bản dữ liệu chuyên sâu với MapReduce "của Jimmy Lin và Chris Dyer.

Tôi đã làm một số nghiên cứu trên google Vấn đề tôi đã được hỏi có tọa độ của thành phố được đề cập trong (x, y) định dạng và nhiều giải pháp tôi thấy trên google xem xét một số yếu tố khác như khoảng cách đơn vị Vì vậy, trong ngắn hạn hơn tôi đã nghiên cứu và đọc tôi bị nhầm lẫn hơn.

Câu hỏi của tôi ở đây là dành cho trường hợp sử dụng dưới đây những gì có thể là giải pháp khả thi và giải pháp tốt nhất trong số em. Nếu một số người có kinh nghiệm có thể đặt một số đèn về điều này nó sẽ rất hữu ích để xóa sự nhầm lẫn của tôi và hiểu giải pháp theo cách tốt hơn. hoặc nếu ai đó có thể trực tiếp tôi để đi đúng hướng (vì vậy mà tôi không bị lẫn lộn nhiều khám phá toàn bộ đại dương của giải pháp)

Sử dụng trường hợp được hỏi trong cuộc phỏng vấn:

Một công ty đang cố gắng tìm giải pháp tối ưu tốt nhất có thể cho phục vụ cơ sở khách hàng của mình là 300 với 12 nhân viên. Họ muốn một giải pháp công nghệ cho biết cách họ có thể đáp ứng yêu cầu của khách hàng vì doanh nghiệp sẽ phát triển và các thay đổi khác như vị trí thay đổi của khách hàng, địa điểm mới được thêm vào v.v.

Vấn đề về cơ bản là một hình thức của vấn đề bán hàng du lịch (TSP) hoặc vấn đề định tuyến xe (VSP). Sau những thứ cần phải được hoàn thành ở đây.

Tọa độ bắt đầu là (0,0) và ví dụ về tọa độ thành phố được đề cập bên dưới. Dưới đây là tọa độ mà giải pháp làm việc dự kiến ​​sẽ được cung cấp trong một file văn bản như là đầu vào:

X coordinate Y Coordinate 
420 278 
421 40 
29 178 
350 47 
298 201 
417 186 
378 134 
447 239 
42 114 
45 199 
362 195 
381 243 
429 1 
338 209 
176 9 
364 26 
326 182 
500 129 
190 51 
489 103 
368 142 
132 260 
305 200 
446 137 
375 154 
440 190 
9 118 
437 32 
383 266 

1. gì có thể đúng cách để xử lý vấn đề này NP-cứng hoặc nếu không đúng cách gì có thể khác nhau tiếp cận với ưu/khuyết điểm của họ.

2. Do có nhiều vấn đề dựa trên phân tích hơn, nên một số loại hình ảnh hóa được thực hiện để giải quyết vấn đề này. Giống như một số biểu đồ hoặc sử dụng các công cụ R/phân tích

Hãy cho tôi biết nếu bạn cần thêm chi tiết hoặc nếu bạn có thể gợi ý nơi tôi có thể đọc và hiểu thêm.

Cảm ơn trước

Answer 1

Tôi không có chuyên môn nhưng có thể bạn không chỉ cần tính toán khoảng cách giữa nguồn gốc và tất cả các điểm khác và tìm điểm gần nhất, sau đó lặp lại quá trình này cho thời điểm đó cho đến khi bạn đã bao phủ tất cả điểm?

Answer 2

Không có cách nào đúng để giải quyết vấn đề NP. Vì tính phức tạp là theo cấp số nhân nên sẽ mất rất nhiều thời gian cho bất kỳ điều gì khác ngoài các ví dụ tầm thường.Tuy nhiên, có xấp xỉ có thể nhận được khá gần với câu trả lời thực sự và có thể đủ tốt cho ứng dụng của bạn (như trong, nó không phải là con đường ngắn nhất, nhưng nó nằm trong phạm vi tương đối của nó).

Kiểm tra wikipedia page của chúng tôi. Họ thậm chí còn có một số ví dụ.

Answer 3

Nếu tôi hỏi câu hỏi này khi phỏng vấn - tôi sẽ đề xuất một số nội dung như được mô tả trong số paper này, có vẻ như phù hợp nhất với công thức của công việc của bạn. Trong bài báo này, bạn sẽ tìm thấy cách tiếp cận gần đúng tối ưu hóa để giải quyết nhiều vấn đề của nhân viên bán hàng với tất cả nhân viên bán hàng bắt đầu từ một điểm. Nó có thể được áp dụng nếu chúng ta biết nơi nhân viên rời đi bằng cách giải quyết từng vấn đề con của nhân viên bán hàng đơn lẻ (phân cụm chia vấn đề chính cho các vấn đề kinh điển) với bắt đầu tại văn phòng nhà/nhà của người bán hàng cụ thể.

Nếu chúng tôi có biểu đồ địa điểm làm đầu vào, không chỉ là tọa độ - chúng tôi có thể thay thế k-means bằng thuật toán phân cụm biểu đồ như MCL.

Answer 4

Thực ra như Dmitry đề cập đến đây là trường hợp của nhiều người đi du lịch. Là NP-hard một cách tự nhiên, người phỏng vấn đang tìm kiếm bạn để đề xuất một thuật toán tối ưu hóa heursitic.

Tôi nghĩ chìa khóa trong trường hợp này là họ đang tìm kiếm một thuật toán có thể cập nhật theo thời gian thực để thay đổi số lượng và vị trí của các điểm đến. thuộc địa Ant optimisaiton (một hình thức tối ưu hóa hạt bầy đàn) đã thực sự bước đầu xây dựng cho các vấn đề nhân viên bán hàng đi du lịch, xem giấy và wikipedia:

https://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms

"M. Dorigo, V. Maniezzo, et A. Colorni, Hệ thống Ant: tối ưu hóa bởi một thuộc tính của các tác nhân hợp tác, Giao dịch IEEE trên Hệ thống, Con người và Điều khiển học - Phần B, tập 26, numéro 1, các trang 29-41, 1996. "

này đã được khái quát hóa từ năm đến nhiều đi du lịch vấn đề saleman xem ví dụ giấy này (mã nguồn mở) cho một số công việc tốt đẹp vào nó:

http://www.researchgate.net/publication/263389346_Multi-type_ant_colony_system_for_solving_the_multiple_traveling_salesman_problem

Trong một tình huống phỏng vấn, tôi sẽ chi tiết nó có Ưu điểm như: 1. là một giải pháp heuristic hiệu quả; 2. Có thể cập nhật theo thời gian thực cho cả hai thay đổi trong biểu đồ; 3. Đối với các điểm thưởng tôi đề cập, khi một giải pháp hợp lý đã thu được trong silico, các trình điều khiển có thể được gán các tuyến theo cách hơi xác suất, sau đó tối ưu hóa được điều khiển bởi dữ liệu thực có thể được thực hiện.

Nhược điểm là một lượng lớn khả năng xử lý hợp lý có thể được yêu cầu so với các vấn đề nói rằng trước tiên giảm không gian tìm kiếm như Dmitry đề xuất. Thứ hai, nếu họ muốn bạn thực sự rút ra một alogirthm này có thể là khá khó khăn trong không gian của một cuộc phỏng vấn.

Câu hỏi thú vị :)