Recent progress of local search in handling the time window constraints of the vehicle routing problem

Vehicle routing and scheduling problems have a wide range of applications and have been intensively studied in the past half century. The condition that enforces each vehicle to start service at each customer in the period specified by the customer is called the time window constraint. This paper reviews recent results on how to handle hard and soft time window constraints, putting emphasis on its different definitions and algorithms. With these diverse time windows, the problem becomes applicable to a wide range of real-world problems.     

Copper ion-induced activation and asymmetric benzoylation of 1,2-diols: kinetic chiral molecular recognition

New catalytic ability of copper(II) ion has been exploited for monobenzoylation of 1,2-diols. The catalyst can be readily modified by ligation to acquire higher stereoselectivity. Highly effective kinetic resolution of dl-1,2-diols was achieved. The enantiodiscrimination process was clearly shown to be controlled by the kinetics of acylation of dl-1,2-diols. The catalytic method was successfully applied to asymmetric desymmetrization of meso-hydrobenzoin.     

Anionic fullerenes, calixarenes, coronenes, and pyrenes as activators of oligo/polyarginines in model membranes and live cells

We report that the efflux of 5(6)-carboxyfluorescein anions from neutral egg yolk phosphatidylcholine vesicles is mediated by oligo/polyarginines only in the presence of activating amphiphilic anions. Screening of anion activators reveals best synergism for amphiphilic carboxylates (fullerene > calix[4]arene approximately coronene > pyrene > calix[6]arene > alkyl), whereas amphiphilic sulfates show less satisfactory activation despite often lower effective concentrations. The analogous alcohols and one calix[4]arene diphosphate were inactive. These results are discussed in the context of a tentative anion carrier mechanism, where interactions with bilayer (interface-directed translocation) and carrier (arene-templated carboxylate-guanidinium pairing) contribute to activator efficiencies. Applied to HeLa cells, pyrenebutyrate is shown to significantly increase the uptake of a fluorescently labeled octaarginine in a concentration-dependent manner.     

Nature of acidic protons in metallosilicate molecular sieves as studied by variable temperature 1H MAS NMR

The dynamic properties of protons in H-[Ga]-ZSM-5, H-[B]-ZSM-5 and H-[Al-B]-ZSM-5 were compared with that of protons in H-[Al]-ZSM-5 by temperature dependence of ¹H MAS NMR in the range of 298 k and 473 K. The temperature dependence of the line width of ¹H MAS NMR reveals that protons in H-[Ga]-ZSM-5 were more mobile than those in H-[Al]-ZSM-5 at temperature as low as 373 K. The protons in H-[B]-ZSM-5 were not mobile at 473 K and fixed in the zeolite frame work as the bridging hydroxyl groups, ≡B-OH-Si≡. The thermal motion of protons in ≡Al-OH-Si≡ was suppressed by introducing B³⁺ cations into the framework of H-[Al]-ZSM-5.     

Determination of ephedrine alkaloid stereoisomers in dietary supplements by capillary electrophoresis

Three complementary capillary electrophoresis (CE) methods were developed for the separation and quantification of ephedrine and pseudoephedrine stereoisomers. Either single or dual cyclodextrin-based chiral selector systems provided enantioselective separation of the compounds of interest. The three methods were applied to the analysis of a suite of five standard reference materials (SRMs) containing ephedra. Use of a high-sensitivity UV detection cell enhanced quantification of the analytes of interest over the wide range of concentrations encountered in the SRMs. Results for (-)-ephedrine ranged from 0.31 to 76.43 mg/g, and for (+)-pseudoephedrine ranged from 0.049 to 9.23 mg/g in the materials studied. Results from the three methods agreed well with each other and with the results from other methods of analysis. The addition of known amounts of specific enantiomers was used to confirm the enantiomeric identity of the analytes. The results obtained by the three CE methods were utilized for value assignment of the ephedrine alkaloid content of these five SRMs.     

Approximation algorithms for combinatorial fractional programming problems

We are concerned with a combinatorial optimization problem which has the ratio of two linear functions as the objective function. This type of problems can be solved by an algorithm that uses an auxiliary problem with a parametrized linear objective function. Because of its combinatorial nature, however, it is often difficult to solve the auxiliary problem exactly. In this paper, we propose an algorithm which assumes that the auxiliary problems are solved only approximately, and prove that it gives an approximate solution to the original problem, of which the accuracy is at least as good as that of approximate solutions to the auxiliary problems. It is also shown that the time complexity is bounded by the square of the computation time of the approximate algorithm for the auxiliary problem. As an example of the proposed algorithm, we present a fully polynomial time approximation scheme for the fractional 0–1 knapsack problem.     

Solvable classes of discrete dynamic programming

As finite state models to represent a discrete optimization problem given in the form of an r-ddp (recursive discrete decision process), three subclasses of r-msdp (recursive monotone sequential decision process) are introduced in this paper. They all have a feature that the functional equations of dynamic programming hold and there exists an algorithm (in the sense of the theory of computation) to obtain the set of optimal policies. (In this sense, we may call them solvable classes of discrete dynamic programming.) Besides the algorithms for obtaining optimal policies, two types of representations are extensively studied for each class of r-msdp's. Other related decision problems are also discussed. It turns out that some of them are solvable while the rest of them are unsolvable.