riokenta0110
16-08-2010, 21:02
Chào các bạn, mình có bài toán sau:
Ở công ty A, nhân viên làm việc ở các trạm theo ca nhiều ngày, mỗi ngày phòng ban X đưa ra 1 danh sách các nhân viên thay ca đi từ Trụ sở chính tới các trạm làm việc và rước các nhân viên khác hết ca từ các trạm này về Trụ sở chính, phòng ban Y phải phân bổ xe chở nhân viên tới các trạm làm việc, và cũng các xe này sẽ rước các nhân viên khác từ các trạm này về (tức là người ta thay ca làm việc). Sơ đồ trạm như sau:
Các trạm phân bố thành các cụm lớn, xem như chi phí di chuyển trong các cụm không đáng kể.
Phòng ban Y phải bố trí nhân viên trên xe và hành trình của mỗi xe làm sao cho tốn ít chi phí nhất.
- Các ràng buộc cứng theo mức ưu tiên sau:
+ Hạn chế tối đa số xe cần huy động. (Mỗi xe có 1 sức chở như nhau - ví dụ tối đa 10 người)
+ Hạn chế tối đa số lần ghé trạm của các xe.(Chi phí ghé trạm rất lớn)
+ Mỗi xe chở chỉ ghé không quá 3 trạm
- Các ràng buộc mềm:
+ Hạn chế xe ghé các trạm khác cụm. (đường xa chi phí lớn)
Ví dụ:
Danh sách phòng ban X đưa ra như sau:
________Lượt đi__Lượt về
Trạm a _____18_____5
Trạm b _____9_____4
Trạm c _____7_____15
Trạm d _____10_____9
Trạm e _____6_____12
Trạm f _____12_____0
Trạm g _____2_____7
...
Lượt đi tổng cộng có: 18+9+7+10+6+12+2 = 64 nhân viên
Lượt về: 5+4+15+9+12+7 = 52 nhân viên
Mỗi xe sức chở tối đa 10 người vậy ta cần 7 xe.
Tiếp theo chúng ta bố trí 64 nhân viên lượt đi lên 7 xe, và sắp xếp hành trình mỗi xe, để trạm đáp cuối làm sao cho thuận tiện nhất để rước 52 nhân viên trong lượt về. Mục đích cuối là giảm chi phí tối thiểu.
Lưu ý là khi xe thả các nhân viên lượt đi xuống tại 1 trạm nào đó thì có thể rướt các nhân viên lượt về lên luôn..
Mình đang bí bài này, nếu bạn nào có ý tưởng thuật toán hay quan tâm thì cùng nhau thảo luận nhé.. thanks.. yes.gif
Ở công ty A, nhân viên làm việc ở các trạm theo ca nhiều ngày, mỗi ngày phòng ban X đưa ra 1 danh sách các nhân viên thay ca đi từ Trụ sở chính tới các trạm làm việc và rước các nhân viên khác hết ca từ các trạm này về Trụ sở chính, phòng ban Y phải phân bổ xe chở nhân viên tới các trạm làm việc, và cũng các xe này sẽ rước các nhân viên khác từ các trạm này về (tức là người ta thay ca làm việc). Sơ đồ trạm như sau:
Các trạm phân bố thành các cụm lớn, xem như chi phí di chuyển trong các cụm không đáng kể.
Phòng ban Y phải bố trí nhân viên trên xe và hành trình của mỗi xe làm sao cho tốn ít chi phí nhất.
- Các ràng buộc cứng theo mức ưu tiên sau:
+ Hạn chế tối đa số xe cần huy động. (Mỗi xe có 1 sức chở như nhau - ví dụ tối đa 10 người)
+ Hạn chế tối đa số lần ghé trạm của các xe.(Chi phí ghé trạm rất lớn)
+ Mỗi xe chở chỉ ghé không quá 3 trạm
- Các ràng buộc mềm:
+ Hạn chế xe ghé các trạm khác cụm. (đường xa chi phí lớn)
Ví dụ:
Danh sách phòng ban X đưa ra như sau:
________Lượt đi__Lượt về
Trạm a _____18_____5
Trạm b _____9_____4
Trạm c _____7_____15
Trạm d _____10_____9
Trạm e _____6_____12
Trạm f _____12_____0
Trạm g _____2_____7
...
Lượt đi tổng cộng có: 18+9+7+10+6+12+2 = 64 nhân viên
Lượt về: 5+4+15+9+12+7 = 52 nhân viên
Mỗi xe sức chở tối đa 10 người vậy ta cần 7 xe.
Tiếp theo chúng ta bố trí 64 nhân viên lượt đi lên 7 xe, và sắp xếp hành trình mỗi xe, để trạm đáp cuối làm sao cho thuận tiện nhất để rước 52 nhân viên trong lượt về. Mục đích cuối là giảm chi phí tối thiểu.
Lưu ý là khi xe thả các nhân viên lượt đi xuống tại 1 trạm nào đó thì có thể rướt các nhân viên lượt về lên luôn..
Mình đang bí bài này, nếu bạn nào có ý tưởng thuật toán hay quan tâm thì cùng nhau thảo luận nhé.. thanks.. yes.gif