Tôi muốn tạo một phần mềm để lập kế hoạch các tuyến xe buýt (và lượng hành khách tối ưu) để vận chuyển trẻ em khuyết tật.

Những chiếc xe buýt này có các thông số kỹ thuật sau:

• m ghế (tối đa 7 - do tài xế và phụ)
• o “Ghế” dành cho xe lăn (tối đa 4)
• Cố định khả năng chịu tải tối đa (ở Áo: 9 hoặc 20 người; ví dụ Ford Transit 9 người; ví dụ Mercedes-Benz Sprinter 20 người)

Thông số tuyến đường:

• Hành trình đến trường của trẻ phải ít hơn 2 giờ (không bao gồm xe buýt công cộng)
• Để tối ưu hóa: cơ chế lai có thể là tối ưu

ví dụ

Tuyến đường tốt nhất 1 là:

• 6, 1, 7, nhóm (2, 3, 4, 5), viện A (lối ra 1, 2, 3, 4, 5, 6), 8, 9, viện B (lối ra 7, 8, 9) hoặc
• 1, 7, 6, Nhóm (2, 3, 4, 5), Trường A (1, 2, 3, 4, 5, 6 đã rút), 8, 9, Trường B (7, 8 đã rút, 9) hoặc
• 7, 1, 6, Nhóm (2, 3, 4, 5), Trường A (Lối ra 1, 2, 3, 4, 5, 6), 8, 9, Trường B (Lối ra 7, 8, 9) hoặc
• ...

Phụ thuộc vào con đường cụ thể (tức là khoảng cách đường giữa các tam giác 1-6-3 và 7-1-6)

Đây là một ví dụ đơn giản. Khi nói đến việc vận chuyển xe lăn, tình hình lại càng phức tạp hơn.

biên tập:
Để ý:Có nhiều hơn 2 trường cao đẳng vì có hơn 9 em. Đây chỉ là ví dụ. Trong thế giới thực, sẽ có 600 trẻ em và 20 tổ chức...

Tôi cần dữ liệu gì?
Dự đoán của tôi là: tọa độ, khoảng cách giữa các điểm (không phải khoảng cách hàng không, mà là khoảng cách đường bộ), loại "sử dụng ghế" (ghế ngồi hoặc xe lăn), một số loại thông số đường (có thể đã lỗi thời do khoảng cách)

Ai đó có thể đề xuất một số ý tưởng, thuật toán, logic, phản hồi (miễn phí! Vì vận chuyển cho trẻ khuyết tật không phải là hoạt động kinh doanh của công ty) mà tôi có thể sử dụng để lấy dữ liệu (ví dụ: tọa độ, khoảng cách...).

Ồ, tôi phải nói. Tôi không phải là kỹ sư phần mềm được đào tạo nên đọc tài liệu có mùi có phần khó khăn, nhưng tôi sẵn sàng bẩn tay!

câu trả lời hay nhất

Thực ra đó là công việc tôi làm để kiếm sống. Về cơ bản, chúng tôi sử dụng MiP và mô hình đường dẫn có tạo cột để giải quyết vấn đề này. Thấy rằng vấn đề nhỏ, tôi nghĩ bạn có thể nhận được kết quả hợp lý bằng cách sử dụng mô hình luồng cạnh đơn giản hơn. Điều này sẽ giúp bạn tiết kiệm được công việc tạo cột, vốn khá tốn công. Trước khi xem xét việc tự mình tạo tuyến đường, tôi khuyên bạn nên tính toán lưu lượng truy cập trên một tuyến đường khởi hành nhất định - trên thực tế, tôi chỉ cần thực hiện việc đó "thủ công" bằng cách sử dụng máy tính tuyến đường và tăng gấp đôi chi phí làm hướng dẫn.

Cụ thể, bạn cần tạo một biểu đồ trong đó mỗi điểm đón và giao hàng là một nút và mỗi tuyến xe buýt là một tập hợp các chú thích được kết nối. Kết nối khi thích hợp, điều này thực sự dễ vẽ hơn là viết :) Sau đó, tạo một hệ thống LP để mô phỏng giao thông, giới hạn lưu lượng truy cập trong khả năng của xe buýt và yêu cầu tất cả hành khách phải được giao hoặc trả tiền nếu không được giao. Giá đắt Vì thế.

Sau khi đã sẵn sàng, hãy tạo các biến bool cho từng tuyến đường và nhân chúng với sức chứa: điều này sẽ cho phép bạn bật và tắt các tuyến xe buýt.

Xin vui lòng tìm hiểu chi tiết, trên đây chỉ là giới thiệu chung.

biên tập:

Chà, sau khi đọc các câu trả lời, tôi đoán tôi phải nói rằng để giải quyết vấn đề này theo cách tôi gợi ý, bạn cần phải có ít nhất một số kiến ​​thức về quy hoạch tuyến tính và lý thuyết đồ thị. vâng đây là mộtRấtVấn đề khó...khó đến mức tôi không nghĩ nó có thể giải được ngoại trừ những hệ thống rất nhỏ sử dụng công nghệ máy tính hiện tại. Thực sự thấy điều nàyĐúngMột cái rất nhỏ. Tôi nghĩ điều đó là có thể và rất vui lòng liên hệ với công ty chúng tôi để được trợ giúp (contact@ange.dk). Tuy nhiên, sự hỗ trợ chuyên nghiệp về tối ưu hóa không hề rẻ.

Nhưng tất cả không bị mất! Có một cách dễ dàng hơn, mặc dù kết quả sẽ không tốt bằng. Khi bạn không thể lập mô hình, hãy mô phỏng! Viết mô phỏng, cho biết tuyến xe buýt, hành khách, v.v., cho thấy hành khách di chuyển dọc theo tuyến xe buýt như thế nào. Để ghi điểm, mỗi chiếc ô tô công cộng bạn sử dụng đều khiến bạn tốn một số tiền, mỗi km bạn sử dụng sẽ khiến bạn mất một số tiền và mỗi hành khách không được vận chuyển sẽ khiến bạn tốn rất nhiều tiền. Sau đó nhìn vào kết quả, thay đổi hướng đi và cố gắng tìm ra giải pháp tốt nhất (rẻ nhất) mà bạn có thể nghĩ ra. Đây có thể không phải là một giải pháp tồi.

Tương tự như vậy, việc tạo ra một chương trình có thể tạo ra giải pháp cho các vấn đề trên ngay từ đầu không phải là một việc làm thích hợp đối với những người không thông thạo lý thuyết đồ thị LP+MiP+. Nhưng có lẽ ít hơn có thể làm được điều đó?

Tôi sẽ nghỉ vào tuần tới hoặc lâu hơn.

Về thuật toán/logic để cân bằng tải và xác định định tuyến xe buýt, chúng tôi tìm thấy một câu hỏi tương tự trên Stack Overflow: https://stackoverflow.com/questions/3253469/