Transportation Science

Nhiều ứng dụng trong giao thông, từ việc ra quyết định đầu tư vốn, lập kế hoạch đội xe đến thiết lập tín hiệu đèn giao thông đều liên quan đến một hình thức thiết kế mạng (lựa chọn rời rạc). Trong bài viết này, chúng tôi xem xét một số ứng dụng và hạn chế của các phương pháp thiết kế mạng dựa trên lập trình số nguyên, đồng thời mô tả một số mô hình và thuật toán lựa chọn rời rạc và liên tục. Mục tiêu của chúng tôi là ba phần: cung cấp một cái nhìn tổng quát để tổng hợp nhiều mô hình thiết kế mạng, đề xuất một khuôn khổ thống nhất để suy diễn nhiều thuật toán thiết kế mạng, và tóm tắt kinh nghiệm tính toán trong việc giải quyết các vấn đề thiết kế. Chúng tôi cũng chỉ ra rằng nhiều bài toán tổ hợp nổi tiếng nhất phát sinh trong kế hoạch giao thông là các chuyên ngành và biến thể của một mô hình thiết kế tổng quát. Do đó, các khái niệm thiết kế mạng được mô tả trong bài viết này có tiềm năng ứng dụng lớn trong nhiều hoàn cảnh vấn đề khác nhau.

Với sự thúc đẩy từ các luật và quy định mới liên quan đến phát thải khí nhà kính, các nhà vận chuyển đang bắt đầu sử dụng xe điện cho việc giao hàng đến tay người tiêu dùng cuối. Các công suất pin hạn chế của những phương tiện này yêu cầu phải ghé qua các trạm sạc trong suốt hành trình giao hàng có chiều dài điển hình của ngành, điều này cần được xem xét trong kế hoạch lộ trình để tránh các tuyến đường phương tiện không hiệu quả với những đoạn đường vòng dài. Chúng tôi giới thiệu bài toán lập lịch tuyến xe điện với các cửa sổ thời gian và các trạm sạc (E-VRPTW), nơi tích hợp khả năng sạc tại bất kỳ trạm nào có sẵn với một sơ đồ sạc phù hợp. Hơn nữa, chúng tôi xem xét công suất tải của xe hạn chế cũng như các cửa sổ thời gian của khách hàng, là những ràng buộc quan trọng nhất trong các ứng dụng logistics thực tế. Như một phương pháp giải quyết, chúng tôi giới thiệu mộtheuristic lai kết hợp thuật toán tìm kiếm hàng xóm biến đổi với một chiến lược tìm kiếm tabu. Các bài kiểm tra được thực hiện trên các trường hợp mới được thiết kế cho E-VRPTW cũng như trên các trường hợp benchmark của các vấn đề liên quan cho thấy hiệu suất cao của heuristic đã đề xuất cũng như tác động tích cực của việc lai ghép.

The maximum covering location model has been used extensively in analyzing locations for public service facilities. The model is extended to account for the chance that when a demand arrives at the system it will not be covered since all facilities capable of covering the demand are engaged serving other demands. An integer programming formulation of the new problem is presented. Several properties of the formulation are proven. A heuristic solution algorithm is presented and computational results with the algorithm are discussed. Directions for future study are also discussed.

Classical facility location models like the P-median problem (PMP) and the uncapacitated fixed-charge location problem (UFLP) implicitly assume that, once constructed, the facilities chosen will always operate as planned. In reality, however, facilities “fail” from time to time due to poor weather, labor actions, changes of ownership, or other factors. Such failures may lead to excessive transportation costs as customers must be served from facilities much farther than their regularly assigned facilities. In this paper, we present models for choosing facility locations to minimize cost, while also taking into account the expected transportation cost after failures of facilities. The goal is to choose facility locations that are both inexpensive under traditional objective functions and also reliable. This reliability approach is new in the facility location literature. We formulate reliability models based on both the PMP and the UFLP and present an optimal Lagrangian relaxation algorithm to solve them. We discuss how to use these models to generate a trade-off curve between the day-to-day operating cost and the expected cost, taking failures into account, and we use these trade-off curves to demonstrate empirically that substantial improvements in reliability are often possible with minimal increases in operating cost.

Một mô hình thời gian rời rạc được trình bày cho bài toán phân bổ giao thông động với một điểm đến duy nhất. Sự ùn tắc được xử lý rõ ràng trong các phương trình lưu lượng. Mô hình là một bài toán lập trình toán học phi tuyến tính và phi lồi. Một phiên bản tuyến tính từng đoạn của mô hình, với một số giả định bổ sung về hàm mục tiêu, có thể được giải cho nghiệm toàn cục bằng cách sử dụng thuật toán simplex một lần—không cần phương pháp branch-and-bound. Chương trình tuyến tính từng đoạn có cấu trúc bậc thang và có thể được giải bằng các kỹ thuật phân rã hoặc phương pháp nén cho các ma trận thưa.

Logistics thành phố nhằm giảm thiểu các phiền toái liên quan đến vận tải hàng hóa ở khu vực đô thị đồng thời hỗ trợ sự phát triển kinh tế và xã hội của chúng. Ý tưởng cơ bản là xem các bên liên quan và quyết định riêng lẻ như là các thành phần của một hệ thống logistics tích hợp. Điều này có nghĩa là cần phải phối hợp giữa các nhà vận chuyển, các hãng vận tải và các chuyến hàng, cũng như hợp nhất hàng hóa của nhiều khách hàng và nhà vận chuyển vào cùng một phương tiện thân thiện với môi trường. Logistics thành phố rõ ràng nhằm tối ưu hóa các hệ thống vận tải đô thị tiên tiến như vậy. Chúng tôi tập trung vào một vấn đề lập kế hoạch logistics thành phố đầy thách thức, đó là lập lịch trình ngắn hạn tích hợp cho các hoạt động và quản lý tài nguyên, trong trường hợp chung liên quan đến cấu trúc phân phối hai tầng. Chúng tôi nghiên cứu các vấn đề chính liên quan đến vấn đề này, giới thiệu một lớp vấn đề mới, đề xuất cả một mô hình tổng quát và các công thức cho các thành phần chính của hệ thống, và xác định các con đường giải pháp đầy hứa hẹn.

Một cuộc điều tra về vấn đề gọi xe theo yêu cầu nhiều đến nhiều với một phương tiện được phát triển thành hai phần (I và II). Phần I tập trung vào trường hợp "tĩnh" của vấn đề. Trong trường hợp này, các yêu cầu trung gian có thể xuất hiện trong quá trình thực hiện tuyến đường không được xem xét. Một hàm mục tiêu tổng quát được khảo sát, đó là việc tối thiểu hóa tổ hợp trọng số giữa thời gian phục vụ tất cả khách hàng và tổng độ "không hài lòng" mà họ trải qua trong thời gian chờ đợi được phục vụ. Độ không hài lòng này được giả định là một hàm tuyến tính của thời gian chờ đợi và thời gian đi của mỗi khách hàng. Các ràng buộc về khả năng chứa của phương tiện và các quy tắc ưu tiên đặc biệt là một phần của vấn đề. Một phương pháp Lập trình Động được phát triển. Thuật toán thể hiện một nỗ lực tính toán mà, mặc dù là một hàm mũ của kích thước vấn đề, thì về tiệm cận là nhỏ hơn so với nỗ lực tương ứng của thuật toán Lập trình Động cổ điển áp dụng cho một Vấn đề Người bán du lịch có cùng kích thước. Phần II mở rộng phương pháp này để giải quyết trường hợp "động" tương đương. Trong trường hợp này, các yêu cầu của khách hàng mới sẽ tự động đủ điều kiện xem xét khi chúng xảy ra. Quy trình là một chuỗi cập nhật mở, mỗi lần theo sau mỗi yêu cầu của khách hàng mới. Thuật toán chỉ tối ưu hóa trên các đầu vào đã biết và không dự đoán yêu cầu của khách hàng trong tương lai. Sự hoãn yêu cầu của khách hàng không xác định được ngăn chặn bởi các quy tắc ưu tiên được giới thiệu trong Phần I. Các ví dụ trong cả hai trường hợp "tĩnh" và "động" được trình bày.

Gần đây, chúng ta đã chứng kiến sự phát triển nhanh chóng của một khối lượng lớn nghiên cứu tập trung vào các cấu trúc vấn đề lập lịch và định tuyến phương tiện với các ràng buộc về thời gian. Mục đích của bài viết này là tổng hợp những tiến bộ đáng kể đã được thực hiện cho các loại vấn đề định tuyến sau đây có thời gian giới hạn: bài toán người bán hàng du lịch đơn và đa, bài toán đường đi ngắn nhất, bài toán cây khung nhỏ nhất, bài toán định tuyến phương tiện tổng quát, bài toán thu gom và giao nhận bao gồm bài toán gọi xe theo yêu cầu, bài toán định tuyến phương tiện theo nhiều kỳ và bài toán bờ biển. Sau khi tổng hợp trạng thái hiện tại trong lĩnh vực này, chúng tôi sẽ đưa ra một số góc nhìn về nghiên cứu trong tương lai.

Gần đây, Daganzo đã giới thiệu mô hình truyền tế bào - một phương pháp đơn giản để mô hình hóa dòng giao thông trên cao tốc, nhất quán với mô hình động lực học. Trong bài báo này, chúng tôi sử dụng mô hình truyền tế bào để xác định vấn đề Phân bổ Giao thông Động Tối ưu Hệ thống (SO DTA) với một điểm đến dưới dạng Lập trình Tuyến tính (LP). Chúng tôi chứng minh rằng mô hình có thể thu được những hiểu biết về vấn đề DTA và chúng tôi đề cập đến các vấn đề liên quan khác nhau, chẳng hạn như khái niệm thời gian di chuyển biên trong một mạng động và các điều kiện cần thiết và đủ cho hệ thống tối ưu. Mô hình được giới hạn ở một điểm đến và, mặc dù nó có thể tính đến các thực tế giao thông như được thể hiện trong mô hình truyền tế bào, nhưng không được trình bày như một mô hình hoạt động cho các ứng dụng thực tế. Mục tiêu chính của bài báo là chứng minh rằng vấn đề DTA có thể được mô hình hóa dưới dạng LP, điều này cho phép sử dụng vast các tài liệu hiện có về LP để hiểu và tính toán DTA tốt hơn. Một ví dụ số minh họa cho tính đơn giản và khả năng áp dụng của phương pháp được đề xuất.

Bài báo này xem xét các nghiên cứu trong 30 năm qua sử dụng các phương pháp nghiên cứu vận hành để giải quyết các vấn đề về định tuyến và lập lịch tàu container ở các cấp độ lập kế hoạch chiến lược, chiến thuật và hoạt động. Các vấn đề này được phân loại và tóm tắt, với trọng tâm là các định dạng mô hình, giả thuyết và thiết kế thuật toán. Bài báo sau đó đưa ra cái nhìn tổng quan về các nghiên cứu liên quan đến quy mô và sự pha trộn của đội tàu container, chiến lược liên minh, và thiết kế mạng lưới (ở cấp độ chiến lược); xác định tần suất, phân bố đội tàu, tối ưu hóa tốc độ và thiết kế lịch trình (ở cấp độ chiến thuật); và đặt chỗ container, định tuyến và điều chỉnh lại lịch trình tàu (ở cấp độ hoạt động). Bài báo cũng làm rõ những nhu cầu của ngành vận tải container theo tuyến cố định và lưu ý khoảng cách giữa các nghiên cứu học thuật hiện có và thực tiễn công nghiệp. Nghiên cứu về định tuyến và lập lịch tàu container chậm hơn so với thực tiễn, đặc biệt là trong bối cảnh sự tăng trưởng nhanh chóng của ngành vận tải container và sự tiến bộ của nghiên cứu vận hành và công nghệ máy tính. Mục đích của bài báo này là để kích thích nhiều nghiên cứu có liên quan đến thực tiễn hơn trong lĩnh vực mới nổi này.