A mixed-integer linear programming approach to the optimization of event-bus schedules: a scheduling application in the tourism sector

This paper deals with “The Enchanted Journey,” which is a daily event tour booked by Bollywood-film fans. During the tour, the participants visit original sites of famous Bollywood films at various locations in Switzerland; moreover, the tour includes stops for lunch and shopping. Each day, up to five buses operate the tour. For operational reasons, however, two or more buses cannot stay at the same location simultaneously. Further operative constraints include time windows for all activities and precedence constraints between some activities. The planning problem is how to compute a feasible schedule for each bus. We implement a two-step hierarchical approach. In the first step, we minimize the total waiting time; in the second step, we minimize the total travel time of all buses. We present a basic formulation of this problem as a mixed-integer linear program. We enhance this basic formulation by symmetry-breaking constraints, which reduces the search space without loss of generality. We report on computational results obtained with the Gurobi Solver. Our numerical results show that all relevant problem instances can be solved using the basic formulation within reasonable CPU time, and that the symmetry-breaking constraints reduce that CPU time considerably.

Genetic Codes with No Dedicated Stop Codon: Context-Dependent Translation Termination

The prevailing view of the nuclear genetic code is that it is largely frozen and unambiguous. Flexibility in the nuclear genetic code has been demonstrated in ciliates that reassign standard stop codons to amino acids, resulting in seven variant genetic codes, including three previously undescribed ones reported here. Surprisingly, in two of these species, we find efficient translation of all 64 codons as standard amino acids and recognition of either one or all three stop codons. How, therefore, does the translation machinery interpret a “stop” codon? We provide evidence, based on ribosomal profiling and “stop” codon depletion shortly before coding sequence ends, that mRNA 3′ ends may contribute to distinguishing stop from sense in a context-dependent manner. We further propose that such context-dependent termination/readthrough suppression near transcript ends enables genetic code evolution.