The urban transit routing problem (UTRP) involves the construction of route sets on existing road networks to cater for the transit demand efficiently. This is an NP-hard problem, where the generation of candidate rou...The urban transit routing problem (UTRP) involves the construction of route sets on existing road networks to cater for the transit demand efficiently. This is an NP-hard problem, where the generation of candidate route sets can lead to a number of potential routes being discarded on the grounds of infeasibility. This paper presents a new repair mechanism to complement the existing terminal repair and the make-small-change operators in dealing with the infeasibility of the candidate route set. When solving the UTRP, the general aim is to determine a set of transit route networks that achieves a minimum total cost for both the passenger and the operator. With this in mind, we propose a differential evolution (DE) algorithm for solving the UTRP with a specific objective of minimizing the average travel time of all served passengers. Computational experiments are performed on the basis of benchmark Mandl’s Swiss network. Computational results from the proposed repair mechanism are comparable with the existing repair mechanisms. Furthermore, the combined repair mechanisms of all three operators produced very promising results. In addition, the proposed DE algorithm outperformed most of the published results in the literature.展开更多
Data center networks may comprise tens or hundreds of thousands of nodes,and,naturally,suffer from frequent software and hardware failures as well as link congestions.Packets are routed along the shortest paths with s...Data center networks may comprise tens or hundreds of thousands of nodes,and,naturally,suffer from frequent software and hardware failures as well as link congestions.Packets are routed along the shortest paths with sufficient resources to facilitate efficient network utilization and minimize delays.In such dynamic networks,links frequently fail or get congested,making the recalculation of the shortest paths a computationally intensive problem.Various routing protocols were proposed to overcome this problem by focusing on network utilization rather than speed.Surprisingly,the design of fast shortest-path algorithms for data centers was largely neglected,though they are universal components of routing protocols.Moreover,parallelization techniques were mostly deployed for random network topologies,and not for regular topologies that are often found in data centers.The aim of this paper is to improve scalability and reduce the time required for the shortest-path calculation in data center networks by parallelization on general-purpose hardware.We propose a novel algorithm that parallelizes edge relaxations as a faster and more scalable solution for popular data center topologies.展开更多
Public transportation network reorganisation can be a key measure in designing more efficient networks and increasing the number of passengers. To date, several authors have proposed models for the “transit route net...Public transportation network reorganisation can be a key measure in designing more efficient networks and increasing the number of passengers. To date, several authors have proposed models for the “transit route network design problem” (TRNDP), and many of them use a transit assignment model as one component. However, not all models have considered the “common lines problem,” which is an essential feature in transit network assignment and is based on the concept that the fastest way to get to a destination is to take the first vehicle arriving among an “attractive” set of lines. Thus, we sought to reveal the features of considering the common lines problem by comparing results with and without considering the problem in a transit assignment model. For comparison, a model similar to a previous one was used, formulated as a bi-level optimisation problem, the upper problem of which is described as a multi-objective problem. As a result, although the solutions with and without considering the common lines showed almost the same Pareto front, we confirmed that a more direct service is provided if the common lines problem is considered whereas a less direct service is provided if it is not. With a small network case study, we found that considering the common lines problem in the TRNDP is important as it allows operators to provide more direct services.展开更多
A campus bus network design and evaluation, taking Tsinghua University as an example, is investigated in this paper. To minimize the total cost for both passengers and operator, the campus bus system planning in a seq...A campus bus network design and evaluation, taking Tsinghua University as an example, is investigated in this paper. To minimize the total cost for both passengers and operator, the campus bus system planning in a sequential approach is discussed, including the route network design, headway （i.e., the inverse of service frequency） optimization, and system evaluation. The improved genetic algorithm is proposed to optimize the route network based on the route property, and the impacts of the fluctuation of passenger demand and average traveling time are analyzed. The identity proportion in the headway optimization is then introduced with full consideration of its impacts. Based on the actual variety of passenger demand, a non-fixed schedule demonstrates its efficiency. VISSIM is finally adopted to simulate the campus bus system and a comprehensive evaluation system for the campus bus is developed. Compared with the current bus network and the one without considering the route property, the evaluation of the proposed approach shows an improvement of 18.7% and 10.1%, respectively. Moreover, the sequential approach shows an efficiency significance for the development of public transit systems passengers and operator. mprovement over the alternative method. It is of great n large industrial parks to decrease the total cost for both展开更多
文摘The urban transit routing problem (UTRP) involves the construction of route sets on existing road networks to cater for the transit demand efficiently. This is an NP-hard problem, where the generation of candidate route sets can lead to a number of potential routes being discarded on the grounds of infeasibility. This paper presents a new repair mechanism to complement the existing terminal repair and the make-small-change operators in dealing with the infeasibility of the candidate route set. When solving the UTRP, the general aim is to determine a set of transit route networks that achieves a minimum total cost for both the passenger and the operator. With this in mind, we propose a differential evolution (DE) algorithm for solving the UTRP with a specific objective of minimizing the average travel time of all served passengers. Computational experiments are performed on the basis of benchmark Mandl’s Swiss network. Computational results from the proposed repair mechanism are comparable with the existing repair mechanisms. Furthermore, the combined repair mechanisms of all three operators produced very promising results. In addition, the proposed DE algorithm outperformed most of the published results in the literature.
基金This work was supported by the Serbian Ministry of Science and Education(project TR-32022)by companies Telekom Srbija and Informatika.
文摘Data center networks may comprise tens or hundreds of thousands of nodes,and,naturally,suffer from frequent software and hardware failures as well as link congestions.Packets are routed along the shortest paths with sufficient resources to facilitate efficient network utilization and minimize delays.In such dynamic networks,links frequently fail or get congested,making the recalculation of the shortest paths a computationally intensive problem.Various routing protocols were proposed to overcome this problem by focusing on network utilization rather than speed.Surprisingly,the design of fast shortest-path algorithms for data centers was largely neglected,though they are universal components of routing protocols.Moreover,parallelization techniques were mostly deployed for random network topologies,and not for regular topologies that are often found in data centers.The aim of this paper is to improve scalability and reduce the time required for the shortest-path calculation in data center networks by parallelization on general-purpose hardware.We propose a novel algorithm that parallelizes edge relaxations as a faster and more scalable solution for popular data center topologies.
文摘Public transportation network reorganisation can be a key measure in designing more efficient networks and increasing the number of passengers. To date, several authors have proposed models for the “transit route network design problem” (TRNDP), and many of them use a transit assignment model as one component. However, not all models have considered the “common lines problem,” which is an essential feature in transit network assignment and is based on the concept that the fastest way to get to a destination is to take the first vehicle arriving among an “attractive” set of lines. Thus, we sought to reveal the features of considering the common lines problem by comparing results with and without considering the problem in a transit assignment model. For comparison, a model similar to a previous one was used, formulated as a bi-level optimisation problem, the upper problem of which is described as a multi-objective problem. As a result, although the solutions with and without considering the common lines showed almost the same Pareto front, we confirmed that a more direct service is provided if the common lines problem is considered whereas a less direct service is provided if it is not. With a small network case study, we found that considering the common lines problem in the TRNDP is important as it allows operators to provide more direct services.
基金supported by the National Natural Science Foundation of China (No.61673233)Beijing Municipal Science and Technology Program (No.D15110900280000)
文摘A campus bus network design and evaluation, taking Tsinghua University as an example, is investigated in this paper. To minimize the total cost for both passengers and operator, the campus bus system planning in a sequential approach is discussed, including the route network design, headway （i.e., the inverse of service frequency） optimization, and system evaluation. The improved genetic algorithm is proposed to optimize the route network based on the route property, and the impacts of the fluctuation of passenger demand and average traveling time are analyzed. The identity proportion in the headway optimization is then introduced with full consideration of its impacts. Based on the actual variety of passenger demand, a non-fixed schedule demonstrates its efficiency. VISSIM is finally adopted to simulate the campus bus system and a comprehensive evaluation system for the campus bus is developed. Compared with the current bus network and the one without considering the route property, the evaluation of the proposed approach shows an improvement of 18.7% and 10.1%, respectively. Moreover, the sequential approach shows an efficiency significance for the development of public transit systems passengers and operator. mprovement over the alternative method. It is of great n large industrial parks to decrease the total cost for both
