International Construction Specialty Conference of the Canadian Society for Civil Engineering (ICSC) (5th : 2015)

A routing algorithm to construct candidate workzones with distance constraints Eicher, Charel; Lethanh, Nam; Adey, Bryan T. Jun 30, 2015

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
52660-Eicher_C_et_al_ICSC15_261_A_Routing_Algorithm.pdf [ 1.9MB ]
Metadata
JSON: 52660-1.0076440.json
JSON-LD: 52660-1.0076440-ld.json
RDF/XML (Pretty): 52660-1.0076440-rdf.xml
RDF/JSON: 52660-1.0076440-rdf.json
Turtle: 52660-1.0076440-turtle.txt
N-Triples: 52660-1.0076440-rdf-ntriples.txt
Original Record: 52660-1.0076440-source.json
Full Text
52660-1.0076440-fulltext.txt
Citation
52660-1.0076440.ris

Full Text

5th International/11th Construction Specialty Conference 5e International/11e Conférence spécialisée sur la construction    Vancouver, British Columbia June 8 to June 10, 2015 / 8 juin au 10 juin 2015   A ROUTING ALGORITHM TO CONSTRUCT CANDIDATE WORKZONES WITH DISTANCE CONSTRAINTS Charel Eicher1, Nam Lethanh2,3, and Bryan T. Adey2 1 Department of Civil, Environmental and Geomatic Engineering, ETH Zürich, Switzerland 2 Institute of Construction and Infrastructure Management, ETH Zürich, Switzerland 3 lethanh@ibi.baug.ethz.ch Abstract: As highways deteriorate over time, it is necessary to execute preventive interventions to ensure that they continue to provide an adequate level of service. As the execution of interventions on highways almost invariably results in the interruption to traffic flow, it is often beneficial to group interventions. By grouping interventions into workzones, there is, for example, less lane changing required by vehicles traveling on the highway and, therefore, perhaps fewer accidents. The objects included in the optimal workzones depend on many factors, such as the condition/performance of the objects, the length of the workzone, the traffic configuration within the workzone, the length of time required to execute the interventions, and the budget available. Recent research by Hajdin & Lindenmann (2007) and Lethanh et al. (2014) has been focused on the development of optimization models to solve such problems. One difficulty with them though is the construction of the set of possible combinations, which was done manually. Once large networks are to be analyzed this is no longer possible. In this paper, a routing algorithm is presented that can be used together with these optimization models to automatically establish the combination matrix, taking into consideration constraints on the length of the workzone and the distance between workzones. The algorithm is developed in Matlab and empirically tested on a real world road network, with 671 km of roads and 567 objects including bridges, tunnels, and road sections. The state of each object is classified on a discrete scale of 5, with 1 being the best and 5 being the worst. Several scenarios based on setting constraints on maximum workzone length, and minimum distance between two adjacent workzones are used to verify the robustness of the algorithm. It is found that the algorithm is both efficient and fast for all scenarios investigated. The development potential, in particular with respect to integration in GISs, is discussed. 1 INTRODUCTION Road networks are comprised of different types of objects, such as road sections, bridges, and tunnels. These objects are subjected to deterioration and, therefore, interventions (e.g. repair, rehabilitation, replacement) need to be executed to ensure that they continue to provide adequate levels of service. When an intervention is executed on an object, a workzone has to be set up to ensure that the intervention can be executed. When there are more than one object on which interventions are to be executed there is the possibility of grouping multiple objects within one work zone. Whether or not they are included, however, depends on their closeness to each other, the benefits of grouping them together as opposed to establishing separate work zones and constraints, such as the amount of funding 261-1  The approach emphasized in these two papers was extended from one work zone to multiple work zones in the work presented by Lethanh et al. (2014), using a mixed-integer linear model. This also involved the introduction of maximum length of a workzone and minimum distance between two adjacent workzones constraints. This work was, however, also done by setting up the continuity and combination matrices manually.  In order to overcome the limitation of having to do this, it is necessary to develop a routing algorithm that allows a computer program to generate the two matrices giving only initial information such as the numbers of objects, numbers of nodes, maximum workzones length, and minimum distance between two adjacent workzones. The goal of the work presented in this paper was to develop such an algorithm.  The remainder of the paper is set-up as follows. The optimization model of Lethanh et al. (2014), which is the model that this work is based on, is described in the following section. Section 3 contains the developed routing algorithm. An example on a road network with 567 objects is shown in Section 4. The last section concludes the paper with highlighted points and elaborates recommendations for future extension of the work. 2 THE MODEL The objective function is [1] , , ,1 1  ( )N Kn k n k n kn kMaximize Z B Cδ= == ⋅ −∑∑  where ,n kδ  is a binary variable, which has a value of 1 if an intervention of type k is executed on road segment n and 0 otherwise. ,n kB  and ,n kC  are the long term benefit and cost of executing an intervention of type k on object n, respectively.  Subject to the following constraints: Continuity [2] ,1 11N Kn kn kδ= ==∑∑  This constraint enforces the model to select only one intervention of k on object n. Budget [3] , ,1 1N Kn k n kn kCδ= =⋅ ≤ Ω∑∑  The budget for executing interventions on the network is in general limited. The total cost of all interventions on the network cannot exceed a certain threshold Ω  for a given planning period. Maximum workzone length [4] ,  w wl nw wl ne eMAXl nl a n awl= =≤ Λ ∀∑ ∑  where ,l nl  is the length of the object [l,n]; ( ) ,w w wl na l a n a= =  is the first object of the workzone (1,..., )w W= , and object; ( ) ,w w wl ne l e n e= =  is the last object in the workzone. MAXΛ  is the maximum length of the workzone. 261-3 Minimum distance [5] ,  d dl nd dl ne eMINl nl a n adl= =≥ Λ ∀∑ ∑  where ( ) ,d d dl na l a n a= =  is the first object the default section d; ( ) ,d d dl ne l e n e= =  is the last object of the default section d; MINΛ  is minimum distance between two workzones. Combination of maximum workzone length and minimum distance The maximum workzone length and the minimum distance between workzones constraint is merged into one constraint by defining a combination matrix of objects within the network that cannot be subjected to an intervention simultaneously. [6] , , ,1 11 N Kn k n k in kiδ γ= =⋅ ≤ ∀∑∑  , ,n k iγ  is a I-by-J matrix, with I is the total number of rows and each row contains an object combination that cannot be selected simultaneously. 3 THE ROUTING ALGORITHM The algorithm was is described in this section using an example of a network comprised of 45 objects and 31 nodes with an equal length of 5 km per object (Figure 2). The maximum length of any workzone and the minimum distance between two adjacent workzones are 15 km. 214693578 12101113 1514 1617 2218 212830 311920232425 26 29271253648711151218 16101713 14919 2021 2829262523223936 37402441 4243453830 3134 353233 Figure 2: A simplified road network of 45 objects In Figure 2, objects and nodes are indicated by numbers with no circles and numbers with circles, respectively. This network is different from the examples used in Hajdin & Adey (2005); Hajdin & Lindenmann (2007); and Lethanh et al. (2014) in that it has loops. The looping structure of the network becomes an obstacle when having to construct the combination and continuity matrices, which represent all possible ways to form a workzone starting from the first object in the workzone. The main task of the proposed algorithm is to calculate all the possible paths in the network taking into consideration both maximum workzone length and minimum distance between two adjacent workzones. Matlab code for each step is publicly available at Github repository2.   3.1 Maximum workzone length For a given object n in the network, the algorithm calculates all paths starting with this object (max-paths). The lengths of these paths are defined as the sum of the lengths of the objects. The paths are then stored 2 https://github.com/namkyodai/workzone-routing-algorithm 261-4                                                      in a matrix format. For example, with object 1, there are in total 6 paths that can be formed (solid thick lines in Figure 3 and combination of objects in Table 1). Table 1: Possible paths starting from object 1 statisfying maximum length Paths 1 2 3 4 5 6 Objects 1 1 1 1 1 1 2 2 3 3 3 3 4 5 4 6 7 10  214693578 12101113 1514 1617 2218 212830 311920232425 26 29271253648711151218 16101713 14919 2021 2829262523223936 37402441 4243453830 3134 353233 Figure 3: All paths starting from object 1 3.2 Minimum distance between two adjacent workzones The algorithm calculates, for a given object n, all paths starting with this object (min-paths). Objects are added to a min-path as long as the min-path’s length is smaller than the minimum distance between workzones. The length of a min-path is defined as the sum of the lengths of its objects minus the length of the first object in the path. Thus the number of objects in the paths for the minimum distance exceeds the number of objects in the paths for the maximum work zone length. Eventually, the total number of paths starting with an object for the minimum distance between workzones is significantly larger than the total number of paths starting with that object for the maximum workzone length. The following figure and table illustrate the matrix formation for the minimum distance constraint. Table 2: Possible min-paths starting after object 1  Paths 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Objects 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 4 4 4 4 5 5 4 4 6 6 7 10 10 10 10 3 6 7 10 6 8 2 5 5 8 0 11 12 15 18  214693578 12101113 1514 1617 2218 212830 311920232425 26 29271253648711151218 16101713 14919 2021 2829262523223936 37402441 4243453830 3134 353233 Figure 4: All paths starting after object 1 261-5 It can be seen that a min-path has its total length greater than the maximum workzone path. For example, path 10 is comprised of objects 3, 6 and 8 with its total length of 15 km. Then if the object 1 is selected to be in a workzone, the other workzone can only be formed after object 8.  3.3 Impossible object combinations After all max-paths and min-paths for all objects in the network have been identified, the algorithm searches for a set of impossible object combinations. Impossible object combinations are pairs of network objects that violate the maximum workzone length constraint if they are to have interventions simultaneously. For example, if object 1 is part of a workzone, impossible object combinations are objects that are too far away to be part of the same workzone as object 1, but too close to be part of an adjacent workzone (they are objects 8, 11, 12, 15, and 18 (Table 3)). Table 3: Impossible object’s combination starting from object 1 Constrains Objects Maximum length 1 2 3 4 5 6 7 - 10 - - - - Minimum distance 1 2 3 4 5 6 7 8 10 11 12 15 18 Invalid combination - - - - - - - 8 - 11 12 15 18 3.4 The combination matrix The combination matrix is a m-by-n matrix where m is the number of constraints and n is the sumproduct of all the objects in the network and the number of intervention. The number of impossible object combinations and thus the number of constraints depends on the difference between the thresholds for the minimum distance between work zones and the maximum work zone length constraints. With increasing difference between these two thresholds, the number of impossible object combinations grows greatly with the number of constraints. Below is an example of the formulation of linear constraints for the impossible combinations with respect to object 1. Table 4: Combination matrix starting from object 1 Objects 1 1 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9 10 10 10 11 11 11 12 12 12Interventions 0 1 0 1 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2Binary 0 1 1 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0WZs 1-8 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1-11 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1-12 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1Combination  Matrix In Table 4, the interventions to be executed on multiple objects can be seen. There are 2 types of interventions for objects 1, and 2, denoted 0 and 1, and 3 types of intervention for objects 7, 8, 10, 11, and 12, denoted 0, 1 and 2. Interventions denoted as “0” are the “do-nothing” interventions, i.e. there is no physical intervention executed and there is no change to the traffic configuration. Interventions denoted 1 and 2 are combinations of a physical intervention type and a traffic configuration. If intervention 1 or intervention 2 is selected, then the object is included in the workzone. Otherwise it is not. The binary values appeared in the combination matrix (refer to Eq. [6]) become 1 when it is impossible to form two workzones adjuscent to each other. This binary value will be multiplied with the binary in the upper part of the table to give a possible workzone. This means that in Table 4, objects 1 are in a work zones, and objects 8, 11 and 12 are not in a work zone.  3.5 The continuity matrix The continuity matrix ensures that exactly one intervention is selected for every object in the network. The continuity matrix is a p-by-n matrix where p is the number of objects in the network and n is the sumproduct of all the objects in the network and the number of intervention.  261-6 Table 5: Continuity matrix Objects 1 1 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9 10 10 10 11 11 11Interventions 0 1 0 1 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2Binary 1 0 1 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 0 1Objects1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 = 22 1 1 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 = 43 1 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 = 64 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 = 65 0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 = 46 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 = 67 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 = 4Continuity matrix The right hand side of the continuity matrix shows the number of connections for every object. For example, object 1 is connected to two adjacent objects and object 2 is connected to four adjacent objects.  3.6 Example results The optimal set of workzones for the simplified example is illustrated in Figure 5. Workzones (shown with thick lines) have been identified and all constraints have been satisfied.  214693578 12101113 1514 1617 2218 212830 311920232425 26 29271253648711151218 16101713 14919 2021 2829262523223936 37402441 4243453830 3134 353233 Figure 5: Result of the simplified example 4 EXAMPLE To demonstrate the robustness and efficiency of the routing algorithm, it was used to determine optimal work zones for a road network comprised of 567 objects with a total length of 671 km was tested.  4.1 Intervention types and condition states Table 6: Condition states-cost and benefit of intervention (per 1 km) CS Road description Low Benefit High Benefit Costs 1 Like new 0 1 1 2 Good 1 2 1 3 Acceptable 2 4 1 4 Insufficient 4 8 1,5 5 Bad 8 16 1,5  261-7 For every object, three types of interventions can be executed: 1) Intervention type 0: Do nothing; 2) Intervention type 1: Low benefit intervention; 2) Intervention type 2: High benefit intervention. All objects are considered to be in one of five discrete states, with worsening physical condition from state 1 to state 5. Executing interventions on objects in state 1 yield low benefits whereas intervening on objects in state 5 yield high benefits. The exact values are given in Table 6. States for objects were randomly generated, but once determined, they were used for all investigated scenarios. 4.2 Scenarios and results Four different scenarios were investigated by means of changes in the budget, the maximum workzone length and the minimum distance between workzones. The optimal sets of workzones were obtained by running the optimization model for these scenarios (Table 7).   Table 7: Scenarios and Results Results Budget (mus3) Maximum workzone length Minimum distance  Number of objects selected Objective function Total number of constraints Unit [ MU/1’000 m] [ m ] [ m ] [ - ] [ MU ] [ - ] Scenario 1 50 5’000 5’000 23 483.3 2’911 Scenario 2 50 5’000 8’000 29 456.2 6’109 Scenario 3 40 6’000 8’000 17 386.6 5’196 Scenario 4 Unlimited 5’000 8’000 176 872.3 6’108  In scenario 1, the budget is restricted to 50 mus, the maximum workzone length and the minimum distance between workzones are set to 5’000 m. For this scenario, the final version of the optimization model, contains a total of 2’911 constraints, and once run the interventions to be executed in the optimal work zones are determined to provide a benefit of 483.3 mus.  In scenario 2, the budget and the maximum workzone length remain unchanged (with respect to scenario 1), whereas the minimum distance between workzones is increased to 8’000 m. Due to this increase, the gap between the minimum distance between workzones and the maximum workzone length increases. The larger gap (3’000 m) between those two workzone constraints causes the number of combination constraints to rise and the total number of constraints reaches 6’109. The number of continuity constraints remains the same for all four scenarios. A slight drop in the value of the objective function is observed from 483.3 to 456.2.  In scenario 3, the minimum distance between workzones remains constant (with respect to scenario 2). The budget is lowered to 40 mus and the maximum workzone length is increased to 6’000 m. This increase reduces the gap between both work zone constraints from 3’000 to 2’000 m and thus the number of impossible object combinations drops again. Scenario 3 has a total of 5’196 constraints. The decrease in the value of the objective function is caused by the reduction in the available budget.  In scenario 4, both workzone length constraints are equal to scenario 2, whereas the budget constraint is lifted. The total number of constraints descreases from 6’109 to 6’108 (no budget constraint).   A strong increase in the total number of objects to have an intervention from 29 to 176 is observed due to the unlimited budget. However, the value of the objective function rises only by a factor of 2. This is because, in the first three scenarios, the objects to have an intervention are mainly in condition states 4 and 5. In scenario 4, a lot of objects in good condition states and thus lower benefits are subject to interventions because of the unrestricted budget.  In all scenarios, computational time was less than 5 minutes on a normal lap top computer (32 bits, 4 GB RAM, Dual-Core Intel 2.53 GHz). This infers the power of computation and robustness of the model with 3 mus stands for monetary units 261-8                                                      beneficial if models developed to solve network problems, such as those developed by Hajdin & Adey (2005); Hajdin & Lindenmann (2007); and Lethanh et al. (2014) are to be expanded to large networks and networks that contain loops. Setting up the combination and continuity matrices, if done manually, is not possible when there are hundreds and thousands of objects in a road network. However, with the developed algorithm (coded in Matlab), they can be generated with ease. In addition, the algorithm allows construction of these two matrices taking into consideration looping structures of a road network.  The algorithm was verified with examples of two simplified road networks: one with a small size network with only 45 objects to describe the algorithm step by step; the other with a large scale network of 567 objects to demonstrate the robustness and efficiency of the algorithm.  With the development of this algorithm a substantial barrier to the implementation of these types of optimisation models has been removed, in the effort to automate the determination of optimal work programs, which are made of work zones, for large road networks. Further work will be focused on testing this algorithm and much larger networks and integrating it into geographical information systems. References Hajdin, R. & Adey, B.T., 2005. An Algorithm to Determine Optimal Highway Worksites Subject to Distance and Budget Constraints. In 84th Annual Meeting of the Transportation Research Board of the United States of America. Washington D.C., United States of America: Transportation Research Board of the United States of America. Hajdin, R. & Lindenmann, H.-P., 2007. Algorithm for the Planning of Optimum Highway Work Zones. Journal of Infrastructure Systems, 13(3), pp.202–214. Lethanh, N., Adey, B.T. & Sigrist, M., 2014. A Mixed-Integer Linear Model for Determining Optimal Work Zones on a Road Network. In Proceeding of the International Conference on Engineering and Applied Sciences Optimization. KOS Island, Greece.   261-10 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.52660.1-0076440/manifest

Comment

Related Items