A greedy random adaptive search procedure for the weighted maximal planar graph problem

The weighted maximal planar graph (WMPG) problem seeks to find a subgraph from a given weighted complete graph such that the subgraph is planar—it can be embedded on the plane without any arcs intersecting. The subgraph is maximal—no additional arc can be added to the subgraph without destroying its planarity and it also has the maximal sum of arc weights. In this paper, the main objective is to develop, implement and empirically analyse a new greedy random adaptive search procedure (GRASP) to solve the WMPG problem. A dynamic strategy to update the restricted candidate list is proposed. An efficient data structure is developed for the Green&Al-Hakim (GH) construction heuristic. The data structure reduces the GH complexity from O(n³) to O(n²). The GH heuristic with the data structure is then integrated with advanced moves neighbourhood to develop an efficient GRASP implementation. Further, we investigate the behaviour of GRASP parameters in relation to the problem's characteristics. Finally, the developed algorithms are compared with the best-known procedures in the literature on a set of 100 test instances of sizes varying from 20 to 100 nodes.     

Developing an efficient algorithm for balancing mass-haul diagrams

A number of linear and integer programming techniques have been used to minimize the total cost of earthwork by considering the various factors involved in the process. Although these models often ensure a global optimum for the problem, they required sophisticated formulations and are quite involved in their setup and definition as well as being expensive computationally and therefore may be of limited use in real life. In construction practice, Mass-haul diagrams (MD) have been an essential tool for planning earthwork construction for many applications including roadwork, piping, and other linear infrastructure facilities. One of the most common heuristics that is used widely by practicing engineers in the field to balance the MD is the “shortest-haul-first” strategy. Balancing the MD using this heuristic is usually carried out either graphically on the drawing, or manually by computing values from the mass-haul diagram itself. However performing this approach graphically or manually is fairly tedious and time consuming. In addition manual and graphical approaches are prone to error. More importantly, if the project considered has a large number of stations (in the order of hundreds), then performing this balance manually becomes impractical. A robust algorithm is therefore needed that can automatically balance the MD. The research discussed here presents a formal definition of an algorithm that uses a sequential pruning technique for automatically computing balances of mass-haul diagrams. It is shown that the new algorithm is more efficient than existing integer programming techniques and computationally runs in level of complexity of O(log n) time in most cases. Thus this algorithm can handle problems with a large number of stations within a reasonable amount of time. In addition, a computer implementation and extensive computational experiments are provided. Suggestions for how this algorithm can be used in cost-based or grade-based optimization of hauling distances and quantities are discussed.