ITS Berkeley

This paper extends the well known Held-Karp's lower bound available for a single Travelling Salesman Problem to the multiple depot case. The LP-relaxation of a symmetric multiple vehicle, multiple depot problem is shown to be lower bounded by an infinite family of bounds. Each lower bound can be computed in a tractable way using a matroid intersection algorithm. When the costs of travelling between any two locations satisfy triangle inequality, it is shown that there exists a 2-approximation algorithm for solving the multiple depot, multiple TSP. These results are useful in solving the...

California boasts nine national parks that are home to a plethora of recreational, cultural, and professional opportunities. It is no surprise that national parks draw in millions of recreational and non-recreational trips from across the country and internationally, however how visitors choose to arrive at these federal lands is a major consideration for land management, policy, and infrastructure decisions. According to the National Park Service’s Visitor Use Statistics, an overwhelming majority of visitors arrive by automobile. Alternative transportation options to national parks in...

This report highlights risk and prioritization factors for housing developments with expiring affordability protections, focused on preserving transit-accessible affordable housing. It presents a regional framework for identifying and preserving subsidized affordable housing in the Southern California Association of Governments (SCAG) region (Los Angeles, Imperial, Orange, Riverside, San Bernardino, and Ventura counties). First, we analyze data from the California Housing Partnership (CHPC) and the National Housing Preservation Database (NHPD) to understand risk factors for expiring...

We study the system optimum dynamic traffic assignment (SODTA) in a network consisting of a freeway and neighboring city streets. There is only one bottleneck in the freeway and every destination is somewhere downstream of the bottleneck. Vehicles can be diverted through off-ramps leading to alternative local street routes. We formulate the problem and determine a graphical solution procedure based on Newell's cumulative plots, which yields the optimal diverted flow over time. On-ramps can be conveniently incorporated in this procedure yielding SO metering rates. The following variants are...