Pickup and delivery problem using metaheuristics techniques

Dial-a-ride problem (DARP) is an optimization problem which deals with the minimization of the cost of the provided service where the customers are provided a door-to-door service based on their requests. This optimization model presented in earlier studies, is considered in this study. Due to the non-linear nature of the objective function the traditional optimization methods are plagued with the problem of converging to a local minima. To overcome this pitfall we use metaheuristics namely Simulated Annealing (SA), Particle Swarm Optimization (PSO), Genetic Algorithm (GA) and Artificial Immune System (AIS). From the results obtained, we conclude that Artificial Immune System method effectively tackles this optimization problem by providing us with optimal solutions. Crown Copyright (C) 2011 Published by Elsevier Ltd. All rights reserved.

On-Chip Memory Architecture Exploration Framework for DSP Processor-Based Embedded System on Chip

Today's SoCs are complex designs with multiple embedded processors, memory subsystems, and application specific peripherals. The memory architecture of embedded SoCs strongly influences the power and performance of the entire system. Further, the memory subsystem constitutes a major part (typically up to 70%) of the silicon area for the current day SoC. In this article, we address the on-chip memory architecture exploration for DSP processors which are organized as multiple memory banks, where banks can be single/dual ported with non-uniform bank sizes. In this paper we propose two different methods for physical memory architecture exploration and identify the strengths and applicability of these methods in a systematic way. Both methods address the memory architecture exploration for a given target application by considering the application's data access characteristics and generates a set of Pareto-optimal design points that are interesting from a power, performance and VLSI area perspective. To the best of our knowledge, this is the first comprehensive work on memory space exploration at physical memory level that integrates data layout and memory exploration to address the system objectives from both hardware design and application software development perspective. Further we propose an automatic framework that explores the design space identifying 100's of Pareto-optimal design points within a few hours of running on a standard desktop configuration.

Scheduling identical parallel machines with machine eligibility restrictions to minimize total weighted flowtime in automobile gear manufacturing

In this paper, we address a scheduling problem for minimizing total weighted flowtime, observed in automobile gear manufacturing. Specifically, the bottleneck operation of the pre-heat treatment stage of gear manufacturing process has been dealt with in scheduling. Many real-life scenarios like unequal release times, sequence dependent setup times, and machine eligibility restrictions have been considered. A mathematical model taking into account dynamic starting conditions has been proposed. The problem is derived to be NP-hard. To approach the problem, a few heuristic algorithms have been proposed. Based on planned computational experiments, the performance of the proposed heuristic algorithms is evaluated: (a) in comparison with optimal solution for small-size problem instances and (b) in comparison with the estimated optimal solution for large-size problem instances. Extensive computational analyses reveal that the proposed heuristic algorithms are capable of consistently yielding near-statistically estimated optimal solutions in a reasonable computational time.

Computational algorithms inspired by biological processes and evolution

In recent times computational algorithms inspired by biological processes and evolution are gaining much popularity for solving science and engineering problems. These algorithms are broadly classified into evolutionary computation and swarm intelligence algorithms, which are derived based on the analogy of natural evolution and biological activities. These include genetic algorithms, genetic programming, differential evolution, particle swarm optimization, ant colony optimization, artificial neural networks, etc. The algorithms being random-search techniques, use some heuristics to guide the search towards optimal solution and speed-up the convergence to obtain the global optimal solutions. The bio-inspired methods have several attractive features and advantages compared to conventional optimization solvers. They also facilitate the advantage of simulation and optimization environment simultaneously to solve hard-to-define (in simple expressions), real-world problems. These biologically inspired methods have provided novel ways of problem-solving for practical problems in traffic routing, networking, games, industry, robotics, economics, mechanical, chemical, electrical, civil, water resources and others fields. This article discusses the key features and development of bio-inspired computational algorithms, and their scope for application in science and engineering fields.

Packet scheduling for priority based transmission in energy harvesting sensors

In this paper, we determine packet scheduling policies for efficient power management in Energy Harvesting Sensors (EHS) which have to transmit packets of high and low priorities over a fading channel. We assume that incoming packets are stored in a buffer and the quality of service for a particular type of message is determined by the expected waiting time of packets of that type of message. The sensors are constrained to work with the energy that they garner from the environment. We derive transmit policies which minimize the sum of expected waiting times of the two types of messages, weighted by penalties. First, we show that for schemes with a constant rate of transmission, under a decoupling approximation, a form of truncated channel inversion is optimal. Using this result, we derive optimal solutions that minimize the weighted sum of the waiting times in the different queues.

Subchannel allocation and power control in femtocells to provide quality of service

Femtocells are a new concept which improves the coverage and capacity of a cellular system. We consider the problem of channel allocation and power control to different users within a Femtocell. Knowing the channels available, the channel states and the rate requirements of different users the Femtocell base station (FBS), allocates the channels to different users to satisfy their requirements. Also, the Femtocell should use minimal power so as to cause least interference to its neighboring Femtocells and outside users. We develop efficient, low complexity algorithms which can be used online by the Femtocell. The users may want to transmit data or voice. We compare our algorithms with the optimal solutions.

Performance evaluation of typical approximation algorithms for nonconvex l(p)-minimization in diffuse optical tomography

The sparse estimation methods that utilize the l(p)-norm, with p being between 0 and 1, have shown better utility in providing optimal solutions to the inverse problem in diffuse optical tomography. These l(p)-norm-based regularizations make the optimization function nonconvex, and algorithms that implement l(p)-norm minimization utilize approximations to the original l(p)-norm function. In this work, three such typical methods for implementing the l(p)-norm were considered, namely, iteratively reweighted l(1)-minimization (IRL1), iteratively reweighted least squares (IRLS), and the iteratively thresholding method (ITM). These methods were deployed for performing diffuse optical tomographic image reconstruction, and a systematic comparison with the help of three numerical and gelatin phantom cases was executed. The results indicate that these three methods in the implementation of l(p)-minimization yields similar results, with IRL1 fairing marginally in cases considered here in terms of shape recovery and quantitative accuracy of the reconstructed diffuse optical tomographic images. (C) 2014 Optical Society of America

Freeform Skeletal Shape Optimization of Compliant Mechanisms

Compliant mechanisms are elastic continua used to transmit or transform force and motion mechanically. The topology optimization methods developed for compliant mechanisms also give the shape for a chosen parameterization of the design domain with a fixed mesh. However, in these methods, the shapes of the flexible segments in the resulting optimal solutions are restricted either by the type or the resolution of the design parameterization. This limitation is overcome in this paper by focusing on optimizing the skeletal shape of the compliant segments in a given topology. It is accomplished by identifying such segments in the topology and representing them using Bezier curves. The vertices of the Bezier control polygon are used to parameterize the shape-design space. Uniform parameter steps of the Bezier curves naturally enable adaptive finite element discretization of the segments as their shapes change. Practical constraints such as avoiding intersections with other segments, self-intersections, and restrictions on the available space and material, are incorporated into the formulation. A multi-criteria function from our prior work is used as the objective. Analytical sensitivity analysis for the objective and constraints is presented and is used in the numerical optimization. Examples are included to illustrate the shape optimization method.

Robust design of multiple trailing edge flaps for helicopter vibration reduction: A multi-objective bat algorithm approach

The objective of this study is to determine an optimal trailing edge flap configuration and flap location to achieve minimum hub vibration levels and flap actuation power simultaneously. An aeroelastic analysis of a soft in-plane four-bladed rotor is performed in conjunction with optimal control. A second-order polynomial response surface based on an orthogonal array (OA) with 3-level design describes both the objectives adequately. Two new orthogonal arrays called MGB2P-OA and MGB4P-OA are proposed to generate nonlinear response surfaces with all interaction terms for two and four parameters, respectively. A multi-objective bat algorithm (MOBA) approach is used to obtain the optimal design point for the mutually conflicting objectives. MOBA is a recently developed nature-inspired metaheuristic optimization algorithm that is based on the echolocation behaviour of bats. It is found that MOBA inspired Pareto optimal trailing edge flap design reduces vibration levels by 73% and flap actuation power by 27% in comparison with the baseline design.

Evaluation and Minimization of Low-Order Harmonic Torque in Low-Switching-Frequency Inverter-Fed Induction Motor Drives

A low-order harmonic pulsating torque is a major concern in high-power drives, high-speed drives, and motor drives operating in an overmodulation region. This paper attempts to minimize the low-order harmonic torques in induction motor drives, operated at a low pulse number (i.e., a low ratio of switching frequency to fundamental frequency), through a frequency domain (FD) approach as well as a synchronous reference frame (SRF) based approach. This paper first investigates FD-based approximate elimination of harmonic torque as suggested by classical works. This is then extended into a procedure for minimization of low-order pulsating torque components in the FD, which is independent of machine parameters and mechanical load. Furthermore, an SRF-based optimal pulse width modulation (PWM) method is proposed to minimize the low-order harmonic torques, considering the motor parameters and load torque. The two optimal methods are evaluated and compared with sine-triangle (ST) PWM and selective harmonic elimination (SHE) PWM through simulations and experimental studies on a 3.7-kW induction motor drive. The SRF-based optimal PWM results in marginally better performance than the FD-based one. However, the selection of optimal switching angle for any modulation index (M) takes much longer in case of SRF than in case of the FD-based approach. The FD-based optimal solutions can be used as good starting solutions and/or to reasonably restrict the search space for optimal solutions in the SRF-based approach. Both of the FD-based and SRF-based optimal PWM methods reduce the low-order pulsating torque significantly, compared to ST PWM and SHE PWM, as shown by the simulation and experimental results.

On optimum stratification with proportional allocation for a class of pareto distributions

Cum ./LSTA_A_8828879_O_XML_IMAGES/LSTA_A_8828879_O_ILM0001.gif rule [Singh (1975)] has been suggested in the literature for finding approximately optimum strata boundaries for proportional allocation, when the stratification is done on the study variable. This paper shows that for the class of density functions arising from the Wang and Aggarwal (1984) representation of the Lorenz Curve (or DBV curves in case of inventory theory), the cum ./LSTA_A_8828879_O_XML_IMAGES/LSTA_A_8828879_O_ILM0002.gif rule in place of giving approximately optimum strata boundaries, yields exactly optimum boundaries. It is also shown that the conjecture of Mahalanobis (1952) “. . .an optimum or nearly optimum solutions will be obtained when the expected contribution of each stratum to the total aggregate value of Y is made equal for all strata” yields exactly optimum strata boundaries for the case considered in the paper.

Robustness of the partitions in grouping multi-item inventories

A recent work obtained closed-form solutions to the.problem of optimally grouping a multi-item inventory into subgroups with a common order cycle per group, when the distribution by value of the inventory could be described by a Pareto function. This paper studies the sensitivity of the optimal subgroup boundaries so obtained. Closed-form expressions have been developed to find intervals for the subgroup boundaries for any given level of suboptimality. Graphs have been provided to aid the user in selecting a cost-effective level of aggregation and choosing appropriate subgroup boundaries for a whole range of inventory distributions. The results of sensitivity analyses demonstrate the availability of flexibility in the partition boundaries and the cost-effectiveness of any stock control system through three groups, and thus also provide a theoretical support to the intuitive ABC system of classifying the items.

Optimal Interconnections in the Design of Microprocessors and Digital Systems

This paper recasts the multiple data path assignment problem solved by Torng and Wilhelm by the dynamic programming method [1] into a minimal covering problem following a switching theoretic approach. The concept of bus compatibility for the data transfers is used to obtain the various ways of interconnecting the circuit modules with the minimum number of buses that allow concurrent data transfers. These have been called the feasible solutions of the problem. The minimal cost solutions are obtained by assigning weights to the bus-compatible sets present in the feasible solutions. Minimization of the cost of the solution by increasing the number of buses is also discussed.

Optimal Interconnections in the Design of Microprocessors and Digital Systems

This paper recasts the multiple data path assignment problem solved by Torng and Wilhelm by the dynamic programming method [1] into a minimal covering problem following a switching theoretic approach. The concept of bus compatibility for the data transfers is used to obtain the various ways of interconnecting the circuit modules with the minimum number of buses that allow concurrent data transfers. These have been called the feasible solutions of the problem. The minimal cost solutions are obtained by assigning weights to the bus-compatible sets present in the feasible solutions. Minimization of the cost of the solution by increasing the number of buses is also discussed.

Active vibration suppression of non-linear beams using optimal dynamic inversion

Euler–Bernoulli beams are distributed parameter systems that are governed by a non-linear partial differential equation (PDE) of motion. This paper presents a vibration control approach for such beams that directly utilizes the non-linear PDE of motion, and hence, it is free from approximation errors (such as model reduction, linearization etc.). Two state feedback controllers are presented based on a newly developed optimal dynamic inversion technique which leads to closed-form solutions for the control variable. In one formulation a continuous controller structure is assumed in the spatial domain, whereas in the other approach it is assumed that the control force is applied through a finite number of discrete actuators located at predefined discrete locations in the spatial domain. An implicit finite difference technique with unconditional stability has been used to solve the PDE with control actions. Numerical simulation studies show that the beam vibration can effectively be decreased using either of the two formulations.