Vehicle Routing Problems that Minimize the Completion Time: Heuristics, Worst-Case Analyses, and Computational Results

In the standard Vehicle Routing Problem (VRP), we route a fleet of vehicles to deliver the demands of all customers such that the total distance traveled by the fleet is minimized. In this dissertation, we study variants of the VRP that minimize the completion time, i.e., we minimize the distance of the longest route. We call it the min-max objective function. In applications such as disaster relief efforts and military operations, the objective is often to finish the delivery or the task as soon as possible, not to plan routes with the minimum total distance. Even in commercial package delivery nowadays, companies are investing in new technologies to speed up delivery instead of focusing merely on the min-sum objective. In this dissertation, we compare the min-max and the standard (min-sum) objective functions in a worst-case analysis to show that the optimal solution with respect to one objective function can be very poor with respect to the other. The results motivate the design of algorithms specifically for the min-max objective. We study variants of min-max VRPs including one problem from the literature (the min-max Multi-Depot VRP) and two new problems (the min-max Split Delivery Multi-Depot VRP with Minimum Service Requirement and the min-max Close-Enough VRP). We develop heuristics to solve these three problems. We compare the results produced by our heuristics to the best-known solutions in the literature and find that our algorithms are effective. In the case where benchmark instances are not available, we generate instances whose near-optimal solutions can be estimated based on geometry. We formulate the Vehicle Routing Problem with Drones and carry out a theoretical analysis to show the maximum benefit from using drones in addition to trucks to reduce delivery time. The speed-up ratio depends on the number of drones loaded onto one truck and the speed of the drone relative to the speed of the truck.

Promoting articulated action from diverse stakeholders in response to public policy scenarios: A case analysis of the use of ‘scenario improvisation’ method

In this paper we present a novel application of scenario methods to engage a diverse constituency of senior stakeholders, with limited time availability, in debate to inform planning and policy development. Our case study project explores post-carbon futures for the Latrobe Valley region of the Australian state of Victoria. Our approach involved initial deductive development of two ‘extreme scenarios’ by a multi-disciplinary research team, based upon an extensive research programme. Over four workshops with the stakeholder constituency, these initial scenarios were discussed, challenged, refined and expanded through an inductive process, whereby participants took ‘ownership’ of a final set of three scenarios. These were both comfortable and challenging to them. The outcomes of this process subsequently informed public policy development for the region. Whilst this process did not follow a single extant structured, multi-stage scenario approach, neither was it devoid of form. Here, we seek to theorise and codify elements of our process – which we term ‘scenario improvisation’ – such that others may adopt it.

Worst-Case Asymmetric Distributed Source Coding

We consider the asymmetric distributed source coding problem, where the recipient interactively communicates with N correlated informants to gather their data. We are mainly interested in minimizing the worst-case number of informant bits required for successful data-gathering at recipient, but we are also concerned with minimizing the number of rounds as well as the number of recipient bits. We provide two algorithms, one that optimally minimizes the number of informant bits and other that trades-off the number of informant bits to efficiently reduce the number of rounds and number of recipient bits.

20 Gb/s mode-group-division multiplexing employing Hermite-Gaussian launches over worst-case multimode fiber links

For the first time, mode group division multiplexing is achieved in a multimode fiber link using a 2-D Hermite-Gaussian mode launch. 20 Gb/s error-free transmission is achieved over a 250 m worst-case OM1 multimode fiber link. © OSA 2014.

Modular average case analysis: Language implementation and extension

Motivated by accurate average-case analysis, MOdular Quantitative Analysis (MOQA) is developed at the Centre for Efficiency Oriented Languages (CEOL). In essence, MOQA allows the programmer to determine the average running time of a broad class of programmes directly from the code in a (semi-)automated way. The MOQA approach has the property of randomness preservation which means that applying any operation to a random structure, results in an output isomorphic to one or more random structures, which is key to systematic timing. Based on original MOQA research, we discuss the design and implementation of a new domain specific scripting language based on randomness preserving operations and random structures. It is designed to facilitate compositional timing by systematically tracking the distributions of inputs and outputs. The notion of a labelled partial order (LPO) is the basic data type in the language. The programmer uses built-in MOQA operations together with restricted control flow statements to design MOQA programs. This MOQA language is formally specified both syntactically and semantically in this thesis. A practical language interpreter implementation is provided and discussed. By analysing new algorithms and data restructuring operations, we demonstrate the wide applicability of the MOQA approach. Also we extend MOQA theory to a number of other domains besides average-case analysis. We show the strong connection between MOQA and parallel computing, reversible computing and data entropy analysis.

Practical programming for static average-case analysis: the MOQA investigation

This work considers the static calculation of a program’s average-case time. The number of systems that currently tackle this research problem is quite small due to the difficulties inherent in average-case analysis. While each of these systems make a pertinent contribution, and are individually discussed in this work, only one of them forms the basis of this research. That particular system is known as MOQA. The MOQA system consists of the MOQA language and the MOQA static analysis tool. Its technique for statically determining average-case behaviour centres on maintaining strict control over both the data structure type and the labeling distribution. This research develops and evaluates the MOQA language implementation, and adds to the functions already available in this language. Furthermore, the theory that backs MOQA is generalised and the range of data structures for which the MOQA static analysis tool can determine average-case behaviour is increased. Also, some of the MOQA applications and extensions suggested in other works are logically examined here. For example, the accuracy of classifying the MOQA language as reversible is investigated, along with the feasibility of incorporating duplicate labels into the MOQA theory. Finally, the analyses that take place during the course of this research reveal some of the MOQA strengths and weaknesses. This thesis aims to be pragmatic when evaluating the current MOQA theory, the advancements set forth in the following work and the benefits of MOQA when compared to similar systems. Succinctly, this work’s significant expansion of the MOQA theory is accompanied by a realistic assessment of MOQA’s accomplishments and a serious deliberation of the opportunities available to MOQA in the future.

Developing a conceptual model of lead performance measurement and benchmarking: A multiple case analysis

Purpose: Environmental turbulence including rapid changes in technology and markets has resulted in the need for new approaches to performance measurement and benchmarking. There is a need for studies that attempt to measure and benchmark upstream, leading or developmental aspects of organizations. Therefore, the aim of this paper is twofold. The first is to conduct an in-depth case analysis of lead performance measurement and benchmarking leading to the further development of a conceptual model derived from the extant literature and initial survey data. The second is to outline future research agendas that could further develop the framework and the subject area.

Design/methodology/approach: A multiple case analysis involving repeated in-depth interviews with managers in organisational areas of upstream influence in the case organisations.

Findings: It was found that the effect of external drivers for lead performance measurement and benchmarking was mediated by organisational context factors such as level of progression in business improvement methods. Moreover, the legitimation of the business improvement methods used for this purpose, although typical, had been extended beyond their original purpose with the development of bespoke sets of lead measures.

Practical implications: Examples of methods and lead measures are given that can be used by organizations in developing a programme of lead performance measurement and benchmarking.

Originality/value: There is a paucity of in-depth studies relating to the theory and practice of lead performance measurement and benchmarking in organisations.

Developing a model of innovation implementation for UK SMEs: A path analysis and explanatory case analysis

Continuous large-scale changes in technology and the globalization of markets have resulted in the need for many SMEs to use innovation as a means of seeking competitive advantage where innovation includes both technological and organizational perspectives (Tapscott, 2009). However, there is a paucity of systematic and empirical research relating to the implementation of innovation management in the context of SMEs. The aim of this article is to redress this imbalance via an empirical study created to develop and test a model of innovation implementation in SMEs. This study uses Structural Equation Modelling (SEM) to test the plausibility of an innovation model, developed from earlier studies, as the basis of a questionnaire survey of 395 SMEs in the UK. The resultant model and construct relationship results are further probed using an explanatory multiple case analysis to explore ‘how’ and ‘why’ type questions within the model and construct relationships. The findings show that the
effects of leadership, people and culture on innovation implementation are mediated by business improvement activities relating to Total Quality Management/Continuous Improvement (TQM/CI) and product and process developments. It is concluded that SMEs have an opportunity to leverage existing quality and process improvement activities to move beyond continuous
improvement outcomes towards effective innovation implementation. The article concludes by suggesting areas suitable for further research.