فرمولاسیون مدل سازی گسسته، برنامه ریزی عدد صحیح و الگوریتم های برنامه ریزی پویا برای زمان بندی سیگنال ترافیک قوی

Traffic volumes are naturally variable and fluctuate from day to day. Robust optimization approaches have been utilized to address the uncertainty in traffic signal timing optimization. However, due to complicated nonlinear programming models, obtaining a global optimal solution is difficult. Instead of working with nonlinear programming models, we propose a discretization modeling approach, where the cycle, green time, and traffic volume are divided into a finite number of discrete values. The robust signal timing problem is formulated as a binary integer program. Two dynamic programming algorithms are then developed. We obtain optimal solutions for all of the instances with respect to the inputs generated from the discretization. Research highlights ► Developed a discretization approach, where the cycle, green time, and traffic volume were divided into a finite number of discrete values. ► Formulated the robust signal timing problem as a binary integer program. ► Designed a dynamic programming algorithm with bi-directional search enhancements. ► Obtained optimal solutions for all of the instances with respect to the inputs generated from the discretization.

Fixed-timed signal control assigns right-of-way at an intersection with pre-determined cycle length, numbers of phases, phase sequences, and individual phase length. While recent studies focus on real-time adaptive signal control, the fixed-timed signal control will still be used for many years due to the costs of detector installation in the adaptive signal control (Smith et al., 2002). In practice, traffic engineers often partition a whole day into several time intervals with relatively stable traffic patterns, such as morning peak, afternoon peak, etc. Certain differential equation techniques (Webster, 1958) and commercial software packages, such as TRANSYT (Vincent et al., 1980), TRANSYT-7F (Wallace et al., 1998) and Synchro (Trafficware, 2003), are then used to investigate timing plans for each time interval. A recent survey on the fixed-timed signal control as well as real-time adaptive control can be found in Papageorgiou et al. (2003). However, real-world traffic demands are fluctuating in nature, even for the same time interval of day and day of week. Yin (2008) collected traffic data during 9–11AM for an intersection of Gainesville, Florida and showed that the traffic flow varies significantly within that time interval. Therefore, it is desirable to consider uncertain demands in the traffic signal optimization. Based on different approaches to address the issue of uncertain traffic demands, existing studies can be classified into four types. Type I is to further partition the time interval into certain sub-intervals; and the traffic demands in each sub-interval are assumed to be constant. The traffic signal optimization is conducted over the whole analysis interval, considering the impacts of the former sub-interval on the subsequent sub-interval. The approaches by Han, 1996 and Wong et al., 2002 belong to Type I. Type II is to incorporate the mean, variance and distribution of traffic volumes into the traffic signal optimization. For example, Park et al., 2001 and Park and Kamarajugadda, 2007 proposed an integration method to incorporate the mean and variance of traffic demands into the Highway Capacity Manual (HCM) delay equation. The integration method was then combined into a genetic algorithm to investigate timing plans. Type III is based on different scenarios, where each scenario represents an observation of traffic demands. The occurrence probability is often assigned to each scenario. The deviation of each scenario from the mean value over all the scenarios is often included into the objective function in order to impose penalties for demand changes. Heydecker, 1987, Ribeiro, 1994 and Ukkusuri et al., 2010, and the mean-variance model of Yin (2008) belong to Type III. The conditional value-at-risk model of Yin (2008) is also scenario-based. However, instead of penalizing the demand deviations, the conditional value-at-risk model is used against high-consequence scenarios. Zhang and Yin (2008) then extended the work to synchronize actuated signals robustly on arterial. Type IV is related to robust optimization notions. Different from the approaches aforementioned, the robust optimization approach does not require accurate demands, demand probability distributions, or a large number of demand scenarios. Only the ranges of uncertain demands are needed. A parameter specified by users can be used to adjust the level of uncertainties. The robust optimization approach often leads to a min–max type of problem. The min–max robust optimization model of Yin (2008) belongs to Type IV. Type I is suitable to situations where traffic volumes are relatively constant in each smaller sub-interval. Type II is appropriate if the demand probability distribution is known. When the demand distribution is unknown, Type III is more relevant if a large number of scenarios are available and the occurrence probability of each scenario is known. In Type IV, only the range of demands is needed. It is relatively easy to obtain the potential range of the uncertain parameters from historical data. For example, when the traffic volume of movement is varied, it is likely to know the potential range, say 100–200 vehicles/h. Type IV has the least requirements on the knowledge of uncertain demands and may be applicable in most situations. The robust optimization has also been applied to certain problems in the transportation sector, such as vehicle routing (Sungur et al., 2008) and road maintenance (Yin et al., 2008). Yin (2008) completed a solid study that used a cutting plane algorithm to solve the robust signal optimization. However, as mentioned in Yin (2008), no globally optimal solution is guaranteed to be found with the cutting plane algorithm. The main difficulty is caused by the min–max model itself. Yin and Lawphongpanich (2007) prove that the cutting plan algorithm is convergent if some sufficient conditions hold. Therefore, the robust optimization problem has to be solved multiple times, each time with a different initial solution to obtain a local optimal solution. In this study, instead of working with continuous nonlinear optimization models, we propose a discretization modeling approach and model the robust signal timing problem using binary integer programs. We show that our approach is able to obtain globally optimal solutions for the min–max model with respect to the discretized inputs. This paper is organized as follows. Section 2 gives the discretization modeling approach. Section 3 describes the integer programming formulation and dynamic programming (DP) algorithms for the min–max model. Numerical studies are presented in Section 4. Section 5 concludes the paper and describes the future research direction.

In this paper, we considered the traffic signal optimization problem with uncertain traffic volumes. Thanks to relatively wide applicability, the robust optimization based model proposed by Yin (2008) was selected to address the uncertain volumes. However, due to the complexity of the nonlinear programming model (Yin, 2008 and Yin and Lawphongpanich, 2007), no globally optimal solution was guaranteed to be found for these models. Instead of working with nonlinear programming models, we proposed a discretization modeling approach, where the cycle, green time, and traffic volume were divided into a finite number of discrete values. When the minimum sampling unit is small, the errors between the discrete approximation and the continuous delay are small. We formulated the robust signal timing problem as a binary integer program. A dynamic programming algorithm was designed for solving the min–max problem. We then proposed an enhanced bi-directional dynamic programming to reduce the computational time. We obtained the global optimal solutions for all the instances with respect to the inputs generated from the discretization. Our approach produced comparable solutions to the continuous model of Yin (2008). The solutions are improved for many instances. The total computational time could be as long as 12 h if the traffic volume range and traffic variation are large, while 20 min are sufficient to finish the computation when the volume range or variation is small. The computational time in such range is acceptable since the computation is conducted offline. As seen in this paper, the dynamic programming suffered from input data with a large range. Future research may investigate the cutting plane technique (Smith et al., 2009) to avoid this problem. The state space relaxation technique (Christofides et al., 1981) may also be used to reduce the computational time in the dynamic programming.